#include<bits/stdc++.h> using namespace std; int m[105][105],n,ans=1E9; void shortestway(int c,int s){ if(c==n){ ans=min(ans,s); return ; } for(int i=1;i<=n;i++){ if(m[c][i]!=-1){ shortestway(i,s+m[c][i]); } } } int main(){ memset(m,-1,sizeof(m)); cin>>n; while(1){ int a,b,c; cin>>a>>b>>c; if(a==0 and b==0 and c==0)break; m[a][b]=c; } shortestway(1,0); cout<<ans; }