#include<bits/stdc++.h> using namespace std; const int maxi=0x7ffff; int f[105][105],w[101][101]; int N,a,b,c; int main() { cin>>N; for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { w[i][j]=maxi; } } cin>>a>>b>>c; while (a!=0&&b!=0&&c!=0) { w[a][b]=c; cin>>a>>b>>c; } for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { f[i][j]=w[i][j]; } } for (int k=1;k<=N;k++) { for (int i=1;i<=N;i++) { for (int j=1;j<=N;j++) { if ((i!=j)&&(i!=k)&&(j!=k)&&(f[i][k]+f[k][j]<f[i][j])) f[i][j]=f[i][k]+f[k][j]; } } } cout<<f[1][N]; return 0; }