http://poj.openjudge.cn/practice/1044

2000ms

65536kB

It is a traditional activity for PKU ACM Team to go hiking during the summer training camp. However, this tradition has been abandoned for several years. To recover this meaningful and interesting hiking tradition, the coach is planning an excursion for this summer. In addition, the new team members strongly urged the team somewhere "exciting". To satisfy their desire, the coach has found a national park and acquired the map of this park. In this map, there are n intersections (numbered from 0 to n-1) connected by m one-way roads. This map has an interesting property that you cannot go back to the intersection you stand now once you leave it. Thus, the map of the park is a typical directed acyclic graph!

So, why is this place exciting? Because some of the roads called "bridges" (they are not true bridges but a jargon referred to the special roads we will soon define below) are dangerous because the bridges may collapse when we walk along them. Don't panic! The safety facilities are adequate and robust, and there is only mentally impact without physical danger. Just have fun!

The excursion will begin at a certain starting intersection s and end at a certain destination intersection t. You can find a route from intersection s to t. A road is called a "bridge" if and only if you cannot find a route from starting intersection to destination once it disappears. The other ordinary roads are not bridges so they are not dangerous at all. According to the experience of the tourists, the danger level of a "bridge" is equal to its length.

Some wicked guys want to make the excursion more dangerous. But wait! A girl is crying! What? A girl? Eventually, PKU ACM team recruited a girl this year! OK... Lady first is a long term policy in PKU ACM team. Boys and girls finally reach a compromise that the excursion should be as safe as possible.

The national park provides an "express" service. The hikers can order at most two buses beforehand to help them to escape some of the most dangerous routes. Each bus can start from anywhere (any intersection or any point on any road) in the national park. But the bus is powered by electricity so it can only travel no more than q meters continuously and the passenger should get off before the electricity runs out. Simply speaking, the team can choose two "express" routes (each starts from anywhere and ends at anywhere), neither of the two routes is more than q meters. When the team is on a bus, the danger level along the route can be ignored.

The problem is reduced to find a route from the start intersection to the end with the least sum of danger levels. On the way we can take two special buses to make our route safe. The routes of two buses can start from anywhere and end at anywhere but the whole team should be put into one bus at one time. Individual activity is forbidden.

The first line contains an integer T (1 ≤ T ≤ 10) -- the number of test cases.

For each test case:
The first line contains five integers n, m, s, t and q (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000, 0 ≤ s,t < n, s ≠ t, 1 ≤ q ≤ 1 000 000 000), indicate the number of intersections, the number of roads, the starting intersection, the end intersection and the limited length of route of a single bus can travel respectively.
The next m lines have the information of all roads in the directed acyclic graph. Each line contains a triple (u,v,w) indicating a road from intersection u to intersection v with length w (1 ≤ w ≤ 1 000) meters.

For each test case, please output a single line containing an integer representing the total danger level of the optimal route. If there is no route from s to t, output "-1" instead.

```1
8 9 0 7 7
0 4 1
0 1 10
1 2 9
4 2 2
2 5 8
4 3 3
5 6 6
5 6 7
6 7 5
```

`1`