1.

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11 
 * Problem: 10099 - The Tourist Guide
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=1040
 * 
 * @author Manuel Hager
 * @version 1.0, 12/30/2010
 * 
 * Method : Ad-Hoc
 * Status : Accepted
 * Runtime:  0.024
 */

#include <iostream>
#include <algorithm>
#define MAX 100

using namespace std;

int graph[MAX][MAX];
int nodes;
int lines;
int c1;
int c2;
int passenger;
int testcase = 1;

int main(int argc, char* argv[]) {
	cin >> nodes >> lines;
	while(!(nodes == 0 && lines == 0)) {
		//reset graph...
		for(int i = 0; i < nodes; i++) {
			for(int j = 0; j < nodes; j++) {
				graph[i][j] = 0;
			}
		}
	
		//add roads...
		for(int i = 0; i < lines; i++) {
			cin >> c1 >> c2 >> passenger, c1--, c2--;
			graph[c1][c2] = graph[c2][c1] = passenger;
		}
		
		//use Floyd�Warshall algorithm
		int min;
		for (int i = 0; i < nodes; i++) {
			for (int j = 0; j < nodes; j++) {
				for (int k = 0; k < nodes; k++) {
					min = graph[j][i] < graph[i][k] ? graph[j][i] : graph[i][k];

					if (min > graph[j][k]) {
						graph[j][k] = min;
					}
				}
			}
		}
		cin >> c1 >> c2 >> passenger, c1--, c2--;
		
		//calculate needed trips...
		int touristsPerTrip = graph[c1][c2] - 1;
		int trips = passenger / touristsPerTrip;
		if(passenger % touristsPerTrip != 0) {
			trips++;
		}
		
		//print result and read next case...
		printf("Scenario #%d\nMinimum Number of Trips = %d\n\n", testcase++, trips);
		cin >> nodes >> lines;
	}
	return 0;
}