#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
struct bian
{
    int x,y,d,next;
} a[21000]; int len,first[110];

void ins(int x,int y,int d)
{
    len++;
    a[len].x=x; a[len].y=y; a[len].d=d;
    a[len].next=first[x]; first[x]=len;
}
int d[110];
int list[110],head,tail;
bool v[110];
int n;
int main()
{
    int x,y,c,m;
    int t,T;
    scanf("%d",&t);
    for(T=1;T<=t;T++)
    {
	    scanf("%d%d",&n,&m);
	    {
	        if(n==0 && m==0) break;
	        len=0; memset(first,0,sizeof(first));
	        for(int i=1;i<=m;i++)
	        {
	            scanf("%d%d%d",&x,&y,&c);
	            ins(x,y,c);
	            ins(y,x,c);
	        }
	        for(int i=1;i<=n;i++) d[i]=999999999;
	        d[1]=0;
	        memset(v,false,sizeof(v));
	        list[1]=1;
	        v[1]=true;
	        head=1; tail=2;
	        while(head!=tail)
	        {
	            x=list[head];
	            for(int k=first[x];k>0;k=a[k].next)
	            {
	                y=a[k].y;
	                if(d[y]>d[x]+a[k].d)
	                {
	                    d[y]=d[x]+a[k].d;
	                    if(v[y]==false)
	                    {
	                        v[y]=true;
	                        list[tail]=y;
	                        tail++; if(tail==n+1) tail=1;
	                    }
	                }
	            }
	            head++; if(head==n+1) head=1;
	            v[x]=false;
	        }
	        printf("Scenario #%d:\n",T);
	        printf("%d\n",d[n]);
	    }
	}
    return 0;
}