The Tourist Guide

### 题目描述 有 $N\ (N\le 100)$ 个城市，城市间有许多条双向通行的道路，每条道路连接两座城市。每条道路还有一个权值 $P\ (P>1)$，表示在该条道路上行驶的车辆被允许的最大载客量。G 先生是一名导游，他想要**亲自**把 $num$ 名旅客从 $S$ 城运往 $T$ 城，问 G 先生最少要运多少趟？  如上图，G 先生想要**亲自**把 $99$ 名旅客从 $1$ 号城运往 $7$ 号城。他应走的路径为 $1-2-4-7$，路径上最大载客量的最小值为 $25$，按理运 $4$ 趟即可。但因为 G 先生也是人，所以实际上每次只能运输 $24$ 名旅客，需要运 $5$ 次。 ### 输入格式 **本题有多组数据**。 对于每组数据： 第一行两个正整数 $N$ 和 $M$，表示城市数量和道路数量。 接下来 $M$ 行，每行三个正整数 $u,v,w$，表示城市 $u$ 和城市 $v$ 由一条最大载客量为 $w$ 的道路连接。 最后一行三个正整数 $S,T,num$，表示要将 $num$ 名旅客从 $S$ 城运往 $T$ 城。 当 $N$ 和 $M$ 为 $0$ 时停止输入。 ### 输出格式 每组数据输出两行： 第一行，输出 “Scenario #x”，x 为当前是第几组数据。 第二行，输出 “Minimum Number of Trips = ans”，ans 为所求答案。 **每组输出最后应输出两次换行。**

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1040 [PDF](https://uva.onlinejudge.org/external/100/p10099.pdf) 



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 99
0 0

Scenario #1
Minimum Number of Trips = 5