> #include <iostream>
> #include<cmath>
> #include<cstring>
> #include<stdlib.h>
> #include<stdio.h>
> using namespace std;
> #define MAX 0x7fffffff
> #define Min(a, b) ((a) < (b) ? (a) : (b))    
> int map[1010][1010],dis[1010];
> int mark[1010];
> int n,m,s,t,W=0;
> void Dijkstra()
> {
>        int i , j , k , min ;
>        for( i = 1 ; i <= n ; i++ )   
>        {
>               mark[i] = 0 ; 
>               if(map[1][i]!=0)  
>               dis[i] = map[1][i] ;
>               else
>               dis[i]=MAX;   
>        }
>        mark[1] = 1 ;
>        for( i = 1 ; i < n ; i++ )   
>        {
>               min = 0; 
>               for( j = 1 ; j <= n ; j++ )
>                      if(!mark[j] && dis[j] > min&&dis[j]!=MAX)
>                      {
>                             min = dis[j];
>                             k = j ;   
>                      }
>               mark[k] = 1;   
>               for( j = 1 ; j <= n ; j++ )     
>                      if(!mark[j] )
>                      {  
>                         int Q;
>                         Q=Min(dis[k],map[k][j]);                         
>                         if(dis[j]<Q&&map[k][j]!=0)
>                         {                                             
>                          dis[j] = Q; 
>                         }   
>                      }
>        }
>               printf("Scenario #%d:\n%d\n\n",W,dis[n]);      
> }
> int main()
> {
>        int i , j , x , y , d,N ;
>        scanf("%d",&N);
>        while(N--)
>        {
>               scanf("%d %d",&n,&m);
>               W++;         
>               memset(map,0,sizeof(map));
>        
>               for( i = 1 ; i <= m ; i++ ) 
>               {
>                      scanf("%d %d %d",&x,&y,&d);
>                      map[x][y] = map[y][x] = d ;
>               }
>               Dijkstra(); 
>        }
>        return 0;
> }