#include<bits/stdc++.h> using namespace std; using pil=pair<int,int>; vector<pil> g[100000]; long long d[100000],s,n,m; void dij(){ for(int i=0;i<=n;i++){ d[i]=2147483647; } d[s]=0; priority_queue<pil,vector<pil>,greater<pil> > minq; minq.push(pil{d[s],s}); while(!minq.empty()){ auto x=minq.top();minq.pop(); long long du=x.first,u=x.second; if(du>d[u]) continue; for(auto e:g[u]){ int v=e.first,w=e.second; if(d[v]>du+w){ d[v]=du+w; minq.push(pil{d[v],v}); } } } } int main(){ cin>>n; s=1; for(;;){ int u,v,w; cin>>u>>v>>w; if(u==0&&v==0&&w==0) break; g[u].push_back(pil{v,w}); } dij(); cout<<d[n]; return 0; }