1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5  6 using namespace std; 7 const int MAXN=110; 8 const int MAXM=10100; 9 const int inf=50000000;10 struct e{11     int u,v,w;12 }edge[MAXM];13 int n,m;14 int s,t,num;15 16 bool cmp(struct e A,struct e B){17     if(A.w>B.w)return true;18     return false;19 }20 int pre[MAXN],rank[MAXN];21 22 int find(int x){23     int r=x;24     while(pre[r]!=-1)25     r=pre[r];26     while(x!=r){27         int q=pre[x];28         pre[x]=r;29         x=q;30     }31     return r;32 }33 34 bool slove(int mid){35     for(int i=0;i<m;i++){36         if(edge[i].w<mid) break;37         int t1=find(edge[i].u);38         int t2=find(edge[i].v);39         if(t1==t2) continue;40         if(rank[t1]>rank[t2]){41             pre[t2]=t1;42         }43         else if(rank[t2]<rank[t1])44         pre[t1]=t2;45         else {46             rank[t2]++;47             pre[t1]=t2;48         }49     }50     if(find(s)==find(t))51     return true;52     return false;53 }54 55 int main(){56     int cas=0;57     int u,v,w;58     while(scanf("%d%d",&n,&m)!=EOF){59         if(n==0&&m==0) break;60         cas++;61         for(int i=0;i<m;i++){62             scanf("%d%d%d",&u,&v,&w);63             edge[i].u=u;edge[i].v=v;64             edge[i].w=w;65         }66         scanf("%d%d%d",&s,&t,&num);67         sort(edge,edge+m,cmp);68         int high=inf,low=0;69         int ans=inf;70         while(low<=high){71             int mid=(low+high)/2;72             memset(pre,-1,sizeof(pre));73             memset(rank,0,sizeof(rank));74             if(slove(mid)){75                 ans=mid; low=mid+1;76             }77             else high=mid-1;78         }79         int a=num/(ans-1)+(num%(ans-1)>0?1:0);80         printf("Scenario #%d\n",cas);81         printf("Minimum Number of Trips = %d\n\n",a);82     }83     return 0;84 }