C :: Heavy Stuff Transportation Company

Time Limit: 10 Seconds Memory Limit: 65536 KB

شرکت “کامیونهای جانسون بزرگ” تولید کنندهی کامیون های بسیار بزرگ است.آخرین مدل تولیدی این شرکت که گودزیلا v12 نام دارد، به اندازه ای بزرگ است که مقدار کالایی که می خواهید با آن جابه جا کنید هیچ وقت به حجم خود کامیون محدود نمی شود اما با توجه به این که جاده ها مقدار محدودی وزن را می توانند تحمل کنند، وزن کالاهای حمل شده توسط کامیون محدود می شود به مقدار وزنی که جاده های مسیری که در آن رانندگی خواهید کرد، تحمل می کنند.

با داشتن شهر مبدا و مقصد،‌شما باید بیشترین مقدار بار گودزیلا v12 را طوری تعیین کنید که مسیری بین شهر مبدا و مقصد وجود داشته باشد که بتواند آن مقدار بار را تحمل کند.

Input

نمونه ی ورودی شامل یک یا چند تست است. خط اول هر تست نمونه شامل دو عدد طبیعی می باشد: تعداد شهرها(2<=n<=200) و تعداد قسمت های جادهها(1<=r<=19900) که شبکه ی مسیرها را می سازند.

در ادامه r خط می آید که هر خط خصوصیات یک جاده را بیان می کند شامل نام های دو شهری که این جاده آن ها را به هم متصل می کند و سپس محدودیت وزنی که این جاده برای کامیونها دارد.نام شهرها بیشتر از ۳۰ کاراکتر نمی باشد و شامل فاصله هم نیستند. محدودیت های وزنی عدد حسابی در بازه ی ۰ تا ۱۰۰۰۰ می باشند. جاده ها نیز دو طرفه می باشند.

آخرین خط ورودی شامل نام شهر مبدا و مقصدی ست که می خواهیم کالا را حمل و نقل کنیم.

نمونه ی ورودی با دو عدد 0 به عنوان n و r پایان می پذیرد.

Output

برای هر تست نمونه، سه خط باید چاپ کنید

· یک خط شامل "Scenario #x" که x شمارهی تست نمونه می باشد.

· یک خط شامل "y tons" که y بیشترین وزن ممکن بار می باشد.

· یک خط خالی

Sample Input

4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
0 0

Sample Output

Scenario #1
80 tons

Scenario #2
170 tons

Submit