#include<cstdio>

#define Max      (100000000)
#define min(x,y) ((x)<(y)?(x):(y))

struct edge
{
    //int x;
    int y,c,next;
}el[1000000];

bool v[1001];
int first[1001];
int d[1001];
int list[1001];
int n,m,head,tail,len,Ans;

void ins(int x,int y,int c)
{
    len+=1;
    /*el[len].x=x;*/el[len].y=y;el[len].c=c;
    el[len].next=first[x];first[x]=len;
}

void Init()
{
    int x,y,c;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        first[i]=-1;
    len=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        ins(x,y,c);
        ins(y,x,c);
    }
    return ;
}

void First()
{
    for(int i=2;i<=n;i++)
    {
        d[i]=0;
        v[i]=false;
    }
    d[1]=Max;
    v[1]=true;
    head=tail=list[1]=1;
    return ;
}

void Spfa()
{
    First();
    int x,y,k;
    while(head<=tail)
    {
        x=list[head];
        k=first[x];
        while(k!=-1)
        {
            y=el[k].y;
            if(d[y]<min(d[x],el[k].c))
            {
                d[y]=min(d[x],el[k].c);
                if(!v[y])
                {
                    tail+=1;
                    list[tail]=y;
                    v[y]=true;
                }
            }
            k=el[k].next;
        }
        v[head]=false;
        head+=1;
    }
    Ans=d[n];
    return ;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        Init();
        Spfa();
        printf("Scenario #%d\n%d\n",i,Ans);
    }
    return 0;
}