#include<iostream> using namespace std; int a,b,c,d,e[11451][11451],f[10005][10005],g[114514],h[114514],i[114514],j,k,l,m,n; int main() { cin>>a;//a结点个数 b边的条数 g[1]=1; g[0]=1; while(g[b]!=0) { b++; cin>>g[b]>>h[b]>>i[b]; } for(c=1;c<=a;c++) { for(d=1;d<=b;d++) { e[c][d]=999999999; e[c][c]=0; f[c][c]=c; } } for(c=1;c<=b;c++) { e[g[c]][h[c]]=i[c]; f[g[c]][h[c]]=g[c]; } for(c=1;c<=a;c++) { for(d=1;d<=a;d++) { for(j=1;j<=a;j++) { if(e[d][c]+e[c][j]<e[d][j]) { e[d][j]=e[d][c]+e[c][j]; f[d][j]=f[c][j]; } } } } cout<<e[1][a]<<endl; //for(c=1;c<=a;c++) //{ //for(d=1;d<=a;d++) //cout<<e[c][d]<<" "; //cout<<endl; //} return 0; }