C – Heavy Transportation

 //改版dijkstra
 #include <iostream>
 #include <algorithm> #define Faster ios::sync_with_stdio(false),cin.tie(0)
 #define Read freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
 #define Close fclose(stdin),fclose(stdout)
 const int maxn = +;
 using namespace std; const int INF = 0xfffff; int mp[maxn][maxn];
 bool v[maxn];
 int n, m;
 int dis[maxn]; void dij(int be){
     int Min, p;
     v[be] = false;
     for(int i = ;i <= n;i++){
         dis[i] = mp[i][be];
     }
     dis[be] = ;     for(int i = ;i <= n;i++){
         Min = ;
         for(int j = ;j <= n;j++){
             if(v[j] && Min < dis[j]){
                 p = j;
                 Min = dis[j];
             }
         }
         if(Min == )
             break;
         v[p] = false;
         for(int j = ;j <= n;j++){
             dis[j] = max(dis[j], min(dis[p],mp[p][j]));
         }
     }
 } int main(){
     Faster;
     int t;
     int cnt = ;
     cin >> t;
     while(t--){
         cnt++;
         cin >> n >> m;
         for(int i = ;i <= n;i++){
             dis[i] = ;
             v[i] = true;
             for(int j = ;j <= n;j++){
                 mp[i][j] = ;
             }
         }
         for(int i = ;i < m;i++){
             int x, y, z;
             cin >> x >> y >> z;
             if(mp[x][y] < z){
                 mp[x][y] = mp[y][x] = z;
             }
         }         dij();
         cout << "Scenario #" << cnt << ":"<< endl;
         cout << dis[n] << endl << endl;
     }
     return ;
 }