1 #include <iostream> 2 #include <vector> 3 #include <queue> 4 #include <utility> 5 #include <algorithm> 6 using namespace std; 7  8 int n; 9 const int size = 35;10 bool vis[size];11 vector< pair<int,int> >ve[size];12 13 int dij( int ban )14 {15     priority_queue< pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > >q;16     q.push( make_pair(0,1) );   17     memset( vis , false , sizeof(vis) );18     vis[ban] = true;19     while( !q.empty() )20     {21         pair<int,int> now = q.top();22         q.pop();23         if( vis[now.second] )24             continue;25         vis[now.second] = true;26         if( now.second==n )27             return now.first;28         int veSize = ve[ now.second ].size();29         for( int i = 0 ; i<veSize ; i++ )30         {31             int next = ve[now.second][i].second;32             int dist = ve[now.second][i].first;33             if (!vis[next])34             {35                 q.push( make_pair( dist+now.first , next) );36             }37         }38     }39     return -1;40 }41 42 int main()43 {44     cin.sync_with_stdio(false);45     int m , a , b , c , sum , ans;46     while( cin >> n >> m &&(n||m) )47     {48         for( int i = 0 ; i<=n ; i++ )49             ve[i].clear();50         for( int i = 0 ; i<m ; i++ )51         {52             cin >> a >> b >> c;53             ve[a].push_back( make_pair(c,b) );54             ve[b].push_back( make_pair(c,a) );55         }   56         ans = -1;57         for( int i = 2 ; i<=n-1 ; i++ )58         {59             sum = dij(i);60             if( sum==-1 )61             {62                 ans = -1;63                 break;64             }65             else66             {67                 ans = max( ans , sum );68             }69         }70         if( ans==-1 )71             cout << "Inf" << endl;72         else73             cout << ans << endl;74     }   75     return 0;76 }