#include <iostream> #include <stdio.h> #include <queue> #define N 1005 using namespace std; int a[N][N]; int n; int d[N]; bool f[N]; void dij(){ int i,j; memset(f,0,sizeof(f)); for(i=1;i<=n;i++){ d[i]=a[1][i]; } f[1]=1; for(i=1;i<n;i++){ int max=-1; int u; for(j=1;j<=n;j++){ if(!f[j]&&d[j]>max){ max=d[j]; u=j; } } f[u]=1; for(j=1;j<=n;j++){ if(!f[j]){ if(a[u][j]>=max) d[j]=max; if(a[u][j]<max){ if(a[u][j]>d[j]) d[j]=a[u][j]; } } } } } int main(){ int t; cin>>t; int i; for(i=1;i<=t;i++){ memset(d,0,sizeof(d)); cin>>n; memset(a,0,sizeof(a)); int m; cin>>m; while(m--){ int st1,st2,w; cin>>st1>>st2>>w; a[st1][st2]=w; a[st2][st1]=w; } dij(); printf("Scenario #%d:\n",i); printf("%d\n\n",d[n]); } return 0; }