1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10099 - The Tourist Guide
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1040
*
* @author Dennis Wilfert
* @version 1.0, 11/02/2009
*
* Method : Floyd Warshall
* Status : Accepted
* Runtime: 0.444
*/
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

class Main {

public static void main(String[] args) throws IOException {

Scanner scanner = new Scanner(new BufferedInputStream(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

int[][] roads;

int N = scanner.nextInt();
int R = scanner.nextInt();

int c1, c2, p, i, j, k, min;

int cases = 1;

while (N != 0) {

roads = new int[N][N];

// Eintragen der Touristenkapazität
for (i = 0; i < R; i++) {
c1 = scanner.nextInt() - 1;
c2 = scanner.nextInt() - 1;
p = scanner.nextInt();

roads[c1][c2] = roads[c2][c1] = p;
}

for (k = 0; k < N; k++) {
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
// Den kürzesten Wege suchen
min = roads[i][k] < roads[k][j] ? roads[i][k] : roads[k][j];

if (min > roads[i][j]) {
roads[i][j] = min;
}
}
}
}
c1 = scanner.nextInt() - 1;
c2 = scanner.nextInt() - 1;
p = scanner.nextInt();

// Ausgeben der nötigen Fahrten. Es muss beachtet werden, dass immer ein Touristenführer mitfährt
writer.println("Scenario #" + cases);
writer.print("Minimum Number of Trips = ");
writer.println((int) Math.ceil((double) p / (double) (roads[c1][c2] - 1)));
writer.println();

cases++;
N = scanner.nextInt();
R = scanner.nextInt();
}

writer.flush();
}
}