#include<iostream>

using namespace std;

const int MAXN = 1200;
const int MAXE = 1200000;

#ifndef _AdjList_
#define _AdjList_
typedef long long EleType;
struct node
{
    int v;
    EleType w;
}edge[MAXE];
int index,pre[MAXN],next[MAXE];
void clear(void)
{
    index=0;
    memset(pre,-1,sizeof(pre));
    memset(next,-1,sizeof(next));
}
void add(int u,int v,EleType w)
{
    edge[index].v=v;
    edge[index].w=w;
    next[index]=pre[u];
    pre[u]=index++;
}
#endif

#ifndef _SPFA_
#define _SPFA_
int Q[MAXE*100];
bool inQ[MAXN];
EleType dist[MAXN];

EleType SPFA(int src,int des)
{
    Q[0]=src;
    int u,v; EleType w;
    memset(inQ,false,sizeof(inQ));
    memset(dist,0,sizeof(dist)); dist[src]=MAXE;
    
    for(int f=0,r=1;f<r;)
    {
        inQ[u=Q[f++]]=false;
        for(int i=pre[u];i!=-1;i=next[i])
        {
            v=edge[i].v;
            w=edge[i].w;
            if(dist[v]<min(dist[u],w))
            {
                dist[v]=min(dist[u],w);
                if(!inQ[v]) inQ[Q[r++]=v]=true;
            }
        }
    }
    
    return dist[des];
}
#endif

EleType w;
int tcase,times=1,n,m,u,v;

int main()
{
    scanf("%d",&tcase);while(tcase--)
    {
        clear();
        scanf("%d %d",&n,&m);
        for(int i=0;m>i;i++)
        {
            scanf("%d %d %I64d",&u,&v,&w);
            add(u-1,v-1,w);
            add(v-1,u-1,w);
        }
        printf("Scenario #%d:\n",times++);
        printf("%I64d\n\n",SPFA(0,n-1));
    }
    return 0;
}