#include<iostream> using namespace std; const int N = 110, inf = 1e9; int f[N][N], n, a, b, c; int main(){ cin >> n; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ f[i][j] = inf; } } while(cin >> a >> b >> c && (a != 0 || b != 0 || c != 0)){ f[a][b] = c; f[b][a] = c; } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ f[i][j] = min(f[i][j], f[i][k] + f[k][j]); } } } cout << f[1][n]; return 0; }