#include<iostream>#include<cstring>#include<queue>using namespace std;#define MAX_INT 1234567890struct node{ int v; int value; //int opposite; int next;};node edge[1000000];queue <int> Q; int flow[1001],head[1001],visit[1001],N;int add(int s,int t,int w){ edge[N].v=t; edge[N].value=w; edge[N].next=head[s]; return N++;}int spfa(int n){ int i,j,k,e,max_flow=0; for(i=1;i<=n;i++) flow[i]=0; Q.push(1); visit[1]=1; flow[1]=MAX_INT; while(!Q.empty()) { e=Q.front(),Q.pop(); visit[e]=0; for(i=head[e];i;i=edge[i].next) { j=edge[i].v; k=(flow[e]<edge[i].value) ? flow[e]:edge[i].value; if(flow[j]<k) { flow[j]=k; if(!visit[j]) { Q.push(j); visit[j]=1; } } } } return flow[n];}int main(){ int i,m,n,s,w,t,count=0,Case; scanf("%d",&Case); while(Case--) { count++; scanf("%d%d",&n,&m); memset(head,0,sizeof(head)); for(N=1,i=0;i<m;i++) { scanf("%d%d%d",&s,&t,&w); head[s]=add(s,t,w); head[t]=add(t,s,w); } printf("Scenario #%d:n%dnn",count,spfa(n)); } return 0;}
