#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
class data
{
public :
int u,e,cst;
bool operator< ( const data & p) const { return cst< p.cst ; }
} ;
vector< int > v[ 210 ] ;
int cost[ 210 ] [ 210 ] ;
char store[ 210 ] [ 35 ] ;
int n,r;
int parent[ 210 ] ;
bool color[ 210 ] ;
void prim( int src,int target)
{
// memset(parent,0,sizeof(parent));
memset ( color,true ,sizeof ( color) ) ;
priority_queue< data> q;
// cout<<src<<" "<<target<<endl;
data temp,current;
vector< int > vnew;
int top= src,a;
color[ src] = false ;
vnew.push_back ( src) ;
while ( vnew.size ( ) ! = n)
{
for ( int i= 0 ; i< v[ top] .size ( ) ; i++ )
{ a= v[ top] [ i] ;
if ( color[ a] == true )
{
// cout<<"Pushed: "<<top<<" "<<v[top][i]<<endl;
temp.u = top;
temp.e = a;
temp.cst = cost[ top] [ a] ;
q.push ( temp) ;
}
}
// if(q.empty()) break;
current= q.top ( ) ;
vnew.push_back ( current.e ) ;
parent[ current.e ] = current.u ;
if ( current.e == target) break ;
color[ current.e ] = false ;
// cout<<current.u<<" >> "<< current.e<<endl;
top= current.e ;
q.pop ( ) ;
}
return ;
}
int main( )
{
map< string,int > m;
int src,target,pos1,pos2,len,d,temp,caseno= 1 ;
char c[ 35 ] ;
bool flag= false ;
while ( scanf ( "%d%d" ,& n,& r) == 2 )
{
if ( n== 0 && r== 0 )
break ;
len= 1 ;
flag= false ;
for ( int i= 0 ; i< r; i++ )
{
scanf ( "%s" ,c) ;
if ( m[ c] ) pos1= m[ c] ;
else pos1= m[ c] = len++ ;
scanf ( "%s" ,c) ;
if ( m[ c] ) pos2= m[ c] ;
else pos2= m[ c] = len++ ;
v[ pos1] .push_back ( pos2) ;
v[ pos2] .push_back ( pos1) ;
scanf ( "%d" ,& d) ;
cost[ pos1] [ pos2] = d;
cost[ pos2] [ pos1] = d;
}
scanf ( "%s" ,c) ;
src= m[ c] ;
scanf ( "%s" ,c) ;
target= m[ c] ;
prim( src,target) ;
int temp_cost= 100000 ;
while ( target! = src)
{
// cout<<target<<endl;
temp= cost[ target] [ parent[ target] ] ;
if ( temp_cost> temp) temp_cost= temp;
target= parent[ target] ;
}
printf ( "Scenario #%d\n %d tons\n \n " ,caseno++ ,temp_cost) ;
memset ( v,0 ,sizeof ( v) ) ;
m.clear ( ) ;
// memset(cost,0,sizeof(cost));
// memset(store,0,sizeof(store));
}
return 0 ;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxjc3RyaW5nPgojaW5jbHVkZTxtYXA+CgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgoKCmNsYXNzIGRhdGEKewoJcHVibGljOgoJCWludCB1LGUsY3N0OwoJYm9vbCBvcGVyYXRvcjwoY29uc3QgZGF0YSAmcCljb25zdCB7IHJldHVybiBjc3Q8cC5jc3Q7fQp9OwoKdmVjdG9yPGludD52WzIxMF07CmludCBjb3N0WzIxMF1bMjEwXTsKY2hhciBzdG9yZVsyMTBdWzM1XTsKaW50IG4scjsKaW50IHBhcmVudFsyMTBdOwpib29sIGNvbG9yWzIxMF07CnZvaWQgcHJpbShpbnQgc3JjLGludCB0YXJnZXQpCnsKLy8JbWVtc2V0KHBhcmVudCwwLHNpemVvZihwYXJlbnQpKTsKCW1lbXNldChjb2xvcix0cnVlLHNpemVvZihjb2xvcikpOwoJcHJpb3JpdHlfcXVldWU8ZGF0YT4gcTsKLy8JY291dDw8c3JjPDwiICI8PHRhcmdldDw8ZW5kbDsKCWRhdGEgdGVtcCxjdXJyZW50OwoJdmVjdG9yPGludD52bmV3OwoJaW50IHRvcD1zcmMsYTsKCWNvbG9yW3NyY109ZmFsc2U7Cgl2bmV3LnB1c2hfYmFjayhzcmMpOwoJd2hpbGUodm5ldy5zaXplKCkhPW4pCgl7CgoJCWZvcihpbnQgaT0wO2k8dlt0b3BdLnNpemUoKTtpKyspCgkJewlhPXZbdG9wXVtpXTsKCQkJaWYoY29sb3JbYV09PXRydWUpCgkJCXsKLy8JCQkJY291dDw8IlB1c2hlZDogIjw8dG9wPDwiICI8PHZbdG9wXVtpXTw8ZW5kbDsKCQkJCXRlbXAudT10b3A7CgoJCQkJdGVtcC5lPWE7CgoJCQkJdGVtcC5jc3Q9Y29zdFt0b3BdW2FdOwoJCQkJcS5wdXNoKHRlbXApOwoJCQl9CgkJfQovLwkJaWYocS5lbXB0eSgpKSBicmVhazsKCgkJY3VycmVudD1xLnRvcCgpOwoKCQl2bmV3LnB1c2hfYmFjayhjdXJyZW50LmUpOwoKCQlwYXJlbnRbY3VycmVudC5lXT1jdXJyZW50LnU7CgkJaWYoY3VycmVudC5lPT10YXJnZXQpIGJyZWFrOwoKCQljb2xvcltjdXJyZW50LmVdPWZhbHNlOwovLwkJY291dDw8Y3VycmVudC51PDwiID4+ICI8PCBjdXJyZW50LmU8PGVuZGw7CgkJdG9wPWN1cnJlbnQuZTsKCQlxLnBvcCgpOwoJfQoKCglyZXR1cm47CgoKfQoKCmludCBtYWluKCkKewoJbWFwPHN0cmluZyxpbnQ+IG07CgoKICAgaW50IHNyYyx0YXJnZXQscG9zMSxwb3MyLGxlbixkLHRlbXAsY2FzZW5vPTE7CiAgIGNoYXIgY1szNV07CgoKICAgYm9vbCBmbGFnPWZhbHNlOwogICAgd2hpbGUoc2NhbmYoIiVkJWQiLCZuLCZyKT09MikKICAgIHsKICAgICAgICBpZihuPT0wICYmIHI9PTApCiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIGxlbj0xOwogICAgICAgIGZsYWc9ZmFsc2U7CiAgICAgICAgZm9yKGludCBpPTA7aTxyO2krKykKICAgICAgICB7CiAgICAgICAgICAgIHNjYW5mKCIlcyIsYyk7CiAgICAgICAgICAgIGlmKG1bY10pIHBvczE9bVtjXTsKICAgICAgICAgICAgZWxzZSBwb3MxPW1bY109bGVuKys7CgogICAgICAgICAgICBzY2FuZigiJXMiLGMpOwogICAgICAgICAgICBpZihtW2NdKSBwb3MyPW1bY107CiAgICAgICAgICAgIGVsc2UgcG9zMj1tW2NdPWxlbisrOwoKICAgICAgICAgICAgdltwb3MxXS5wdXNoX2JhY2socG9zMik7CiAgICAgICAgICAgIHZbcG9zMl0ucHVzaF9iYWNrKHBvczEpOwogICAgICAgICAgICBzY2FuZigiJWQiLCZkKTsKICAgICAgICAgICAgY29zdFtwb3MxXVtwb3MyXT1kOwogICAgICAgICAgICBjb3N0W3BvczJdW3BvczFdPWQ7CiAgICAgICAgfQoKICAgICAgICBzY2FuZigiJXMiLGMpOwoJCXNyYz1tW2NdOwoKCQlzY2FuZigiJXMiLGMpOwogICAgICAgIHRhcmdldD1tW2NdOwoKICAgICAgICBwcmltKHNyYyx0YXJnZXQpOwogICAgICAgIGludCB0ZW1wX2Nvc3Q9MTAwMDAwOwogICAgICAgIHdoaWxlKHRhcmdldCE9c3JjKQogICAgICAgIHsKLy8JCQljb3V0PDx0YXJnZXQ8PGVuZGw7CgkJCXRlbXA9Y29zdFt0YXJnZXRdW3BhcmVudFt0YXJnZXRdXTsKCQkJaWYodGVtcF9jb3N0PnRlbXApIHRlbXBfY29zdD10ZW1wOwoJCQl0YXJnZXQ9cGFyZW50W3RhcmdldF07CgkJfQoJCXByaW50ZigiU2NlbmFyaW8gIyVkXG4lZCB0b25zXG5cbiIsY2FzZW5vKyssdGVtcF9jb3N0KTsKCgkJbWVtc2V0KHYsMCxzaXplb2YodikpOwoJCW0uY2xlYXIoKTsKLy8JCW1lbXNldChjb3N0LDAsc2l6ZW9mKGNvc3QpKTsKLy8JCW1lbXNldChzdG9yZSwwLHNpemVvZihzdG9yZSkpOwogICAgfQogICAgcmV0dXJuIDA7Cgp9Cgo=