1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define maxn 1050
19 const int inf = 1 << 30;
20 int n, m;
21 int maz[maxn][maxn];
22 int dist[maxn];
23 bool visit[maxn];
24 void prim(int s) {
25     memset(visit, false, sizeof(visit));
26     memset(dist, -1, sizeof(dist));
27     dist[s] = inf;
28     while(1) {
29         int u = -1;
30         for(int i = 1; i <= n; i++)
31             if(!visit[i] && (u == -1 || dist[i] > dist[u])) 
32                 u = i;
33         if(u == -1) break;
34         visit[u] = true;
35         for(int i = 1; i <= n; i++) {
36             if(!visit[i] && maz[u][i] != -1)
37                 dist[i] = max(dist[i], min(dist[u], maz[u][i]));
38         }
39     }
40 }
41 
42 int main() {
43     int T, Case = 1;
44     int u, v, w;
45     scanf("%d", &T);
46     while(T--) {
47         memset(maz, -1, sizeof(maz));
48         scanf("%d%d", &n, &m);
49         for(int i = 0; i < m; i++) {
50             scanf("%d%d%d", &u, &v, &w);
51             maz[u][v] = maz[v][u] = w;
52         }
53         prim(1);
54         printf("Scenario #%d:\n%d\n\n", Case++, dist[n]);
55     }
56     return 0;
57 }
58