#include<iostream> using namespace std; const int BM = 110, inf = 1e9; int n, f[BM][BM], a, b, c, dis[BM]; bool vis[BM]; int main(){ for(int i = 0; i < BM; i++){ for(int j = 0; j < BM; j++){ f[i][j] = inf; } dis[i] = inf; 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 = inf; while(true){ d = -1, e = inf; for(int i = 1; i <= n; i++){ if(dis[i] < e && !vis[i]){ d = i; e = dis[i]; vis[i] = true; } } if(d == -1) break; for(int i = 1; i <= n; i++){ if(!vis[i]){ dis[i] = min(dis[i], dis[d] + f[d][i]); } } } cout << dis[n]; return 0; }