1291. Heavy Cargo

#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[550];
struct edge
{
    int u,v,w;
};
bool cmp (edge a,edge b)
{
    return a.w>b.w;
}
void ini()
{
    for (int i=1;i<=n;i++) f[i]=i;
}
int getf(int u)
{
    return f[u]==u?u:f[u]=getf(f[u]);
}
void merge(int u,int v)
{
    int uf=getf(u),vf=getf(v);
    if (uf!=vf) f[v]=uf;
}
edge e[19901];
int main()
{   
    int q=0;
    while(cin>>n>>m)
    {
        q++;
        if (n==0 && m==0) break;
        ini();
        unordered_map<string,int> mp;
        int cnt=1;
        for (int i=1;i<=m;i++)
        {
            string U,V;
            int w;
            cin>>U>>V>>w;
            if (mp[U]==0) mp[U]=cnt++;
            if (mp[V]==0) mp[V]=cnt++;
            e[i].u=mp[U];
            e[i].v=mp[V];
            e[i].w=w;
        }
        string SS,EE;
        cin>>SS>>EE;
        int S=mp[SS],E=mp[EE];
        sort(e+1,e+1+m,cmp);
        bool f=0;
        int ans;
        for (int i=1;i<=m && !f;i++)
        {
            edge tmp=e[i];
            ans=tmp.w;
            merge(e[i].u,e[i].v);
            if (getf(S)==getf(E)) f=1;
        }
        cout<<"Scenario #"<<q<<endl<<ans<<" tons"<<endl<<endl;
    }
    return 0;
}