/* ***********************************************

 Author        :Sun Yuefeng

 Created Time  :2016/10/22 20:09:36

 File Name     :A.cpp

 ************************************************ */

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #include<string>

 #include<bitset>

 #include<map>

 #include<set>

 #include<stack>

 #include<vector>

 #include<queue>

 #include<list>

 #define M(a,b) memset(a,b,sizeof(a))

 using namespace std;

 typedef long long ll;

 const int inf=0x3f3f3f3f;

 const int maxn=1e3+;

 const int mod=1e7+;

 int dx[]= {,,,-,,-,,-};

 int dy[]= {,-,,,-,,,-};

 int n,m;

 int way[maxn][maxn];

 int dis[maxn];

 bool vis[maxn];

 void dijkstra(){

     for(int i=;i<=n;i++){

         dis[i]=way[i][];

         vis[i]=false;

     }

     for(int i=;i<=n;i++){

         int k=-;

         int mi=-;

         for(int j=;j<=n;j++){

             if(!vis[j]&&dis[j]>mi){

                 mi=dis[j];

                 k=j;

             }

         }

         vis[k]=true;

         for(int j=;j<=n;j++){

             if(dis[j]<min(dis[k],way[j][k])&&!vis[j])

                 dis[j]=min(dis[k],way[j][k]);

         }

     }

     printf("%d\n\n",dis[n]);

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int T,_case=;

     scanf("%d",&T);

     while(T--){

         M(way,-);

         printf("Scenario #%d:\n",_case++);

         int u,v,w;

         scanf("%d%d",&n,&m);

         for(int i=;i<m;i++){

             scanf("%d%d%d",&u,&v,&w);

             way[u][v]=way[v][u]=w;

         }

         dijkstra();

     }

     return ;

 }