#include<iostream>
#include<algorithm>
#include<vector>
#define val 110
int status[val];
#define infinity 99999999
int n,r,s,d,t;
int dist[val][val];
using namespace std;
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a>b?b:a;
}
 
void reset_dist()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			  dist[i][j]=0;
		}
	}
}
void maximin_path()
{
 
for (int k=1; k<=n; k++)
  for (int i=1; i<=n; i++)
    for (int j=1; j<=n; j++)
      dist[i][j] = max(dist[i][j], min(dist[i][k], dist[k][j]));
}
int main()
{ 
    int v1,v2,wt,m;
    int tst=0;
    while(cin>>n>>r)
    {
    	if((n==0)&&(r==0))
    	   break;
    	reset_dist();
    	tst++;
    	for(int i=1;i<=r;i++)
    	{
    	   cin>>v1>>v2>>wt;
		   dist[v1][v2]=wt;
		   dist[v2][v1]=wt;
 
    	}
    	maximin_path();
        cin>>s>>t>>d;
        if(d==0)
        {
        	m=0;
        }
        if((s!=t)&&(d!=0))
        {
        int p=(dist[s][t]-1);
        if(d%p==0)
        {
        	m=d/p;
        }
        else 
        {
        	m=(d/p)+1;
        }
		}
		if((s==t)&&(d!=0))
		{
			m=1;
		}
        cout<<"Scenario #"<<tst<<"\n";
        cout<<"Minimum Number of Trips = "<<m<<"\n";
        cout<<"\n";
    }
   return 0;
}
 

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8dmVjdG9yPgojZGVmaW5lIHZhbCAxMTAKaW50IHN0YXR1c1t2YWxdOwojZGVmaW5lIGluZmluaXR5IDk5OTk5OTk5CmludCBuLHIscyxkLHQ7CmludCBkaXN0W3ZhbF1bdmFsXTsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG1heChpbnQgYSxpbnQgYikKewoJcmV0dXJuIGE+Yj9hOmI7Cn0KaW50IG1pbihpbnQgYSxpbnQgYikKewoJcmV0dXJuIGE+Yj9iOmE7Cn0KCnZvaWQgcmVzZXRfZGlzdCgpCnsKCWZvcihpbnQgaT0xO2k8PW47aSsrKQoJewoJCWZvcihpbnQgaj0xO2o8PW47aisrKQoJCXsKCQkJICBkaXN0W2ldW2pdPTA7CgkJfQoJfQp9CnZvaWQgbWF4aW1pbl9wYXRoKCkKewoJCmZvciAoaW50IGs9MTsgazw9bjsgaysrKQogIGZvciAoaW50IGk9MTsgaTw9bjsgaSsrKQogICAgZm9yIChpbnQgaj0xOyBqPD1uOyBqKyspCiAgICAgIGRpc3RbaV1bal0gPSBtYXgoZGlzdFtpXVtqXSwgbWluKGRpc3RbaV1ba10sIGRpc3Rba11bal0pKTsKfQppbnQgbWFpbigpCnsgCiAgICBpbnQgdjEsdjIsd3QsbTsKICAgIGludCB0c3Q9MDsKICAgIHdoaWxlKGNpbj4+bj4+cikKICAgIHsKICAgIAlpZigobj09MCkmJihyPT0wKSkKICAgIAkgICBicmVhazsKICAgIAlyZXNldF9kaXN0KCk7CiAgICAJdHN0Kys7CiAgICAJZm9yKGludCBpPTE7aTw9cjtpKyspCiAgICAJewogICAgCSAgIGNpbj4+djE+PnYyPj53dDsKCQkgICBkaXN0W3YxXVt2Ml09d3Q7CgkJICAgZGlzdFt2Ml1bdjFdPXd0OwoJCSAgIAkKICAgIAl9CiAgICAJbWF4aW1pbl9wYXRoKCk7CiAgICAgICAgY2luPj5zPj50Pj5kOwogICAgICAgIGlmKGQ9PTApCiAgICAgICAgewogICAgICAgIAltPTA7CiAgICAgICAgfQogICAgICAgIGlmKChzIT10KSYmKGQhPTApKQogICAgICAgIHsKICAgICAgICBpbnQgcD0oZGlzdFtzXVt0XS0xKTsKICAgICAgICBpZihkJXA9PTApCiAgICAgICAgewogICAgICAgIAltPWQvcDsKICAgICAgICB9CiAgICAgICAgZWxzZSAKICAgICAgICB7CiAgICAgICAgCW09KGQvcCkrMTsKICAgICAgICB9CgkJfQoJCWlmKChzPT10KSYmKGQhPTApKQoJCXsKCQkJbT0xOwoJCX0KICAgICAgICBjb3V0PDwiU2NlbmFyaW8gIyI8PHRzdDw8IlxuIjsKICAgICAgICBjb3V0PDwiTWluaW11bSBOdW1iZXIgb2YgVHJpcHMgPSAiPDxtPDwiXG4iOwogICAgICAgIGNvdXQ8PCJcbiI7CiAgICB9CiAgIHJldHVybiAwOwp9Cg==

NyAxMAoxIDIgMzAKMSAzIDE1CjEgNCAxMAoyIDQgMjUKMiA1IDYwCjMgNCA0MAozIDYgMjAKNCA3IDM1CjUgNyAyMAo2IDcgMzAKMSA3IDAKNSA2CjIgNCA0NQoxIDIgMzUKMSAzIDE5CjIgNSA5NgozIDUgMjgKMiAzIDE3CjEgMSAxMDAKNSA2CjIgNCA0NQoxIDIgMzUKMSAzIDE5CjIgNSA5NgozIDUgMjgKMiAzIDE3CjEgNSAxMDAKNSA3CjEgNCAxMAoyIDQgNDUKMSAyIDM1CjEgMyAxOQoyIDUgOTYKMyA1IDI4CjIgMyAxNwoxIDUgMTAwCjUgNgoyIDQgNDUKMSAyIDM1CjEgMyAxOQoyIDUgOTYKMyA1IDI4CjIgMyAxNwo1IDIgMjUKNSA2CjIgNCA0NQoxIDIgMzUKMSAzIDE5CjIgNSA5NgozIDUgMjgKMiAzIDE3CjIgMiA5CjUgNgoyIDQgNDUKMSAyIDM1CjEgMyAxOQoyIDUgOTYKMyA1IDI4CjIgMyAxNwozIDMgMQo1IDcKMSA0IDEwCjIgNCA0NQoxIDIgMzUKMSAzIDE5CjIgNSA5NgozIDUgMjgKMiAzIDE3CjEgNSAyCjUgNgoyIDQgNDUKMSAyIDM1CjEgMyAxOQoyIDUgOTYKMyA1IDI4CjIgMyAxNwo1IDIgODgKMCAw

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 0
5 6
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
1 1 100
5 6
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
1 5 100
5 7
1 4 10
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
1 5 100
5 6
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
5 2 25
5 6
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
2 2 9
5 6
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
3 3 1
5 7
1 4 10
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
1 5 2
5 6
2 4 45
1 2 35
1 3 19
2 5 96
3 5 28
2 3 17
5 2 88
0 0