#include <iostream>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <queue>
#include <vector>
#include <algorithm>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define ll long long
#define ld long double
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lcm(a,b) ((a)*(b)/(__gcd((a),(b))))
#define mod 1000000007
#define MP make_pair
#define PI pair<int,int>
using namespace std;
const int N = 1e6 + 10;
int t, n, m, k = 1, num, vis[N], dis[N], mp[1010][1010];
priority_queue<PI, vector<PI>, greater<PI> > q;
void dijkstra(int s) {
    dis[s] = INF;
    q.push(MP(INF, s));
    while(!q.empty()) {
        int w = q.top().first;
        int v = q.top().second;
        vis[v] = 1;
        q.pop();
        for(int i = 1; i <= n; i++) {
            if(mp[v][i]) {
                if(!vis[i] && dis[i] < min(w, mp[v][i])) {
                    dis[i] = min(w, mp[v][i]);
                    q.push(MP(dis[i], i));
                }
            }
        }
    }
}
int main() {
    IOS
    cin >> t;
    while(t--) {
        me(vis), me(dis), me(mp);
        cin >> n >> m;
        for(int a, b, c, i = 0; i < m; i++) {
            cin >> a >> b >> c;
            if(mp[a][b] < c) {
                mp[a][b] = mp[b][a] = c;
            }
        }
        dijkstra(1);
        cout << "Scenario #" << k++ << ":" << endl;
        if(n == 1)
            dis[1] = 0;
        cout << dis[n] << endl << endl;
    }
    return 0;
}