1112 - Mice and Maze

實驗室中的老鼠被訓練要逃離迷宮，迷宮由許多個小房間相連構成。然而有許多障礙物在房間的通道中，如果要經過會有時間上的罰分。老鼠只會有一種方式去抵達另一個房間，不會有其他的方式。

假設所有老鼠現在正在被訓練， 放置於任何一個迷宮中的房間，規劃一條路使得牠們能在最短時間內抵達終點的房間。

即將做以下的實驗：將老鼠放置每一個房間，並且按下倒數計時器，當時間停止時，計算所有逃離迷宮的老鼠個數。

寫一個程式去計算老鼠個數，根據給定的迷宮以及時間限制。假設每個點都可以抵達終點，而所有房間都可以有任意數量的老鼠，

Input 

輸入第一行會有一個整數，表示接下來會有幾組測資，測資組間會有一行空白行。

每組第一行會有一個整數 N ( N ≤ 100 )，表示小房間的個數，編號為 1, 2, ..., N
第二行會有一個整數 E，表示終點房間的編號，
第三行會有一個整數 T，表示時間倒數的秒數。
第四行會有一個整數M，表示連接兩房間的個數。
接下來會有 M 行，每行上會有三個整數 a, b, time，表示 a 到 b 需要花費 time 的時間，單向的道路。

Output 

對於每組測資，輸出逃離迷宮的老鼠個數，測資組間空一行。

Sample Input 

1

4 
2 
1
8
1 2 1
1 3 1
2 1 1
2 4 1
3 1 1
3 4 1
4 2 1
4 3 1

Sample Output 

3