#include  < iostream >
#include  < algorithm >
#include  < limits >

int   n,m;
int   graph[ 1001 ][ 1001 ];
bool  visite[ 1001 ];
int   result[ 1001 ];

void  shortpath()
{
    memset( visite,  false ,  sizeof (visite) );
    memset( result,  0 ,  sizeof (result) );

    visite[ 1 ] =   true ;

     for  (  int  i =   1 ; i <=  n;  ++ i )
            result[i] =  graph[ 1 ][i];

     for  (  int  i =   1 ; i <  n;  ++ i )
     {
         int  max =   0 ;
         int  k =   - 1 ;

         for  (  int  j =   1 ; j <=  n;  ++ j )
             if  (  ! visite[j]  &&  result[j] >  max )
             {
                max =  result[j];
                k =  j;
            }

        visite[k] =   true ;
         for  (  int  j =   1 ; j <=  n;  ++ j )
             if  (  ! visite[j]  &&  graph[k][j] >   0    &&  result[j] <  std::min( result[k], graph[k][j] ) )
                result[j] =  std::min ( result[k], graph[k][j]);
    }

}

int  main()
{
     int  test;
    scanf( " %d " , & test);

     for  (  int  t =   1 ; t <=  test;  ++ t )
     {
        scanf( " %d%d " , & n, & m);
        memset( graph,  0 ,  sizeof (graph) );

         for  (  int  i =   0 ; i <  m;  ++ i )
         {
             int  x, y,d;
            scanf( " %d%d%d " , & x, & y, & d);

            graph[x][y] =  d;
            graph[y][x] =  d;
        }

        shortpath();
        printf( " Scenario #%d:\n " , t );
        printf( " %d\n " , result[n] );
        printf( " \n " );
    }

     return   0 ;
}