#include<bits/stdc++.h> using namespace std; const int BM=133; int n,f[BM][BM],a,b,c,dis[BM]; bool v[BM]; int main() { for(int i=0;i<BM;i++)//初始化 { for(int j=0;j<BM;j++) { f[i][j]=1e9; } dis[i]=1e9; f[i][i]=0; } dis[1]=0; cin>>n; while(cin>>a>>b>>c&&(a!=0||b!=0||c!=0)) { f[a][b]=c; } int d=-1,e=1e9; while(true) { d=-1,e=1e9; for(int i=1;i<=n;i++) { if(dis[i]<e&&!v[i]) { d=i; e=dis[i]; } } if(d==-1)break; v[d]=true; for(int i=1;i<=n;i++) { if(!v[i])dis[i]=min(dis[i],dis[d]+f[d][i]); } } cout<<dis[n]; }