int ji=i-j,ki=i-k;

        f[j][k]=max(f[j][k],f[j-][k-]);

        f[j][k]=max(f[j][k],f[j-][k]);

        f[j][k]=max(f[j][k],f[j][k-]);

        f[j][k]+=s[j][ji];

        if(j!=k&&ji!=ki) f[j][k]+=s[k][ki];

#include<cstdio>

#include<iostream>

#include<algorithm>

#define R register int

using namespace std;

int n,cnt,f[][],s[][];

struct node {

    int u,v,w;

}a[];

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=(ret<<)+(ret<<)+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

inline int max(int a,int b) {return a>b?a:b;}

signed main() {

    n=g(); R u=g(),v=g(),w=g();

    while(u&&v&&w) {a[++cnt].u=u,a[cnt].v=v,a[cnt].w=w;u=g(),v=g(),w=g();}

    for(R i=;i<=cnt;i++) {s[a[i].u][a[i].v]=a[i].w;}

    for(R i=;i<=(n<<);i++) for(R j=i;j>=;j--) for(R k=i;k>=;k--) {

        R ji=i-j,ki=i-k;

        f[j][k]=max(f[j][k],f[j-][k-]);

        f[j][k]=max(f[j][k],f[j-][k]);

        f[j][k]=max(f[j][k],f[j][k-]);

        f[j][k]+=(s[j][ji]+s[k][ki]*(j!=k));

    } printf("%d\n",f[n][n]);

}