Let's Catch the Party!

We are given the road network of the country. There are ~N~ cities (numbered from ~1~ to ~N~ and ~M~ one-way roads connecting pairs of different cities. For each road, we know the time (in hours) it takes to travel from one end to the other. We want to travel from city ~S~, where we live, to city ~T~, where our best friend is having a party. However, we see with great sadness that we won't make it to the party, which will take place in ~B~ hours! We definitely don't want to miss the party!

Luckily, a good fairy appears. She offers us the following deal: we will give her a subset of the roads, and she will use her magic so that we can travel these roads in zero time! However, for each road the fairy "zeros out," we will have to do a good deed (e.g., help run the PDP camp for a year after we finish school!), and we don't want to commit to doing too many good deeds!

Find the minimum number of roads we need to ask the fairy to "zero out" so that we can make it to our friend's party in time!

Input:

The first line of the input will contain five natural numbers ~N~, ~M~, ~S~, ~T~, and ~B~, separated in pairs by a space: the number of cities, the number of roads, the starting city, the destination city, and the number of hours we have before our friend's party.

Each of the next ~M~ lines describes a one-way road. It contains three integers ~U_i~, ~V_i~, and ~T_i~, separated in pairs by a space. Such a line means that we can travel from city ~U_i~ to city ~V_i~ and this trip will take ~T_i~ hours.

Assume it will always be possible to travel from city ~S~ to city ~T~.

Output:

The output must contain a single line with exactly one integer: the minimum number of roads we will ask the fairy to "zero out" in order to make it to our friend's party on time.

Constraints:

• ~1 \le N \le 1.000~.
• ~1 M \le 10.000~.
• ~1 \le B \le 1.000.000.000~.
• ~1 \le S \le N~, ~1 \le T \le N~, ~1 \le T \le N~, ~S \neq T~.
• ~1 \le U_i \le N~, \(1 \le V_i​\le N\), ~U_i \neq V_i~.
• ~1 \le T_i \le 2.000.000~.
• There will not be more than one road with the same endpoints and the same direction.
• The sum of all ~T_i~ will not exceed ~1.000.000.000~.
• Time Limit: ~1~ sec.
• Memory Limit: ~256~ MB.
• For test cases with a total value of ~30%~, θα υπάρχει ακριβώς μία διαδρομή με αφετηρία την πόλη ~S~ και τερματισμό την πόλη ~T~.
• For test cases with a total value of ~30%~, it will be ~N \le 100~, ~M \le 1.000~.

Example of Input - Ouput:

input:

6 9 3 6 15
2 1 4
3 2 7
4 5 6
1 3 8
1 4 4
5 2 8
5 6 10
1 5 5
4 2 5

output:

2

Explanation of the example:

We want to go from city ~3~ to city ~6~ and we have ~15~ hours available. If we ask the fairy to "zero out" the roads ~3 \to 2~ and ~2 \to 1~, then we can arrive exactly in ~15~ hours. There is no way to manage it by zero-ing out fewer than two roads.