#include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn =  + ;

 int n, m, k, Case = , G[maxn][maxn], dist[maxn];

 bool vis[maxn];

 int Dijkstra(int source, int aid) {

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

         dist[i] = (i == source ? INF : );

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

         int minf = -;

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

             if(!vis[j] && minf < dist[j]) {

                 minf = dist[j];

                 k = j;

             }

         vis[k] = true;

         if(minf == - ) break;

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

             if(!vis[j] && dist[j] < min(dist[k], G[k][j]))

                 dist[j] = min(dist[k], G[k][j]);

     }

     return dist[aid];

 }

 int main () {

     int t, x, y, w;

     scanf("%d", &t);

     while(t --) {

         memset(vis, false, sizeof vis);

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

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

                 G[i][j] = ;

         }

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

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

             scanf("%d %d %d", &x, &y, &w);

             G[x][y] = G[y][x] = max(G[x][y], w);

         }

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

     }

     return ;

 }