团队远足

题目描述:

给定一张N个点M条边的有向无环图，每条边都有一个长度。给定一个起点S和终点T。若从S到T的每条路径都经过某条边，则称这条边是有向图的必经边或桥。

现在要从S点到T点。他们在路上可以搭乘两次车。每次可以从任意位置（甚至是一条边上的任意位置）上车，从任意位置下车，但连续乘坐的长度不能超过q米。除去这两次乘车外，剩下的路段步行。定义从S到T的路径的危险程度等于步行经过的桥上路段的长度之和。求从S到T的最小危险程度是多少。

输入格式:

第一行包括5个整数 n, m, s, t 和 q (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000, 0 ≤ s,t < n, s ≠ t, 1 ≤ q ≤ 1 000 000 000), 分别表示顶点个数、道路的条数、起始点编号、终点编号，每次乘车最长的距离。

接下来m行描述一个有向无环图，每行包括三个数u,v,w，表示从u顶点到v顶点有条道路，长度是w米，  (1 ≤ w ≤ 1 000) 。

输出格式:

一行一个整数，表示最小的危险程度。如果没有路径，输出-1。

样例输入:

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

样例输出:

3

提示:

1<=N , M <=2*10⁵, 1<=1 <= 10⁹。

时间限制: 1000ms
空间限制: 256MB

---