UVA1112 Mice and Maze

实验室的老鼠正在接受逃离迷宫的训练。迷宫由若干单元组成，每个单元与其他一些单元通过通道相连。通过通道需要消耗一定的时间。此外，通道是单向的。 假设所有老鼠都会选择一条耗时最短的路径到达出口单元。 我们将进行以下实验：在迷宫的每个单元中放置一只老鼠，并启动倒计时计时器。当倒计时计时器的数值为零结束时，我们统计已经逃出迷宫的老鼠数量。 编写一个程序，预测将有多少只老鼠能够逃出迷宫。假设单元可以容纳任意数量的老鼠。

输入以一个正整数开始，表示测试组数。 每组数据之间用空行分隔。 每组测试数据的输入格式如下： 前三行输入 $N,E,T$，其中 $N$（$N \le 100$）表示迷宫中的单元的总数；$E$ 表示出口单元的编号；$T$ 倒计时计时器的初始值。 迷宫中的单元编号为 $1,2,\cdots,N$。 第四行一个整数 $M$，表示迷宫中有多少个通道。 接下来 $M$ 行每行三个整数，前两个整数 $a,b$ 分别表示这个通道的起点和终点，第三个整数表示消耗的时间。 注意，每个连接是单向的，即老鼠不能从 $b$ 移动到 $a$，除非存在另一个通道是从 $b$ 到 $a$ 的。 此外，两个方向的时间消耗可能不同。

对于每组数据，输出一行，表示在时间 $T$ 内到达出口单元 $E$ 的老鼠数量。 两个连续测试数据的输出之间用一个空行分隔。