题目背景

试题来源：http://poj.openjudge.cn/practice/1044

题目描述

北大 ACM 队有一个传统活动：在夏令营期间去徒步旅行。然而，这一传统已经被搁置了好几年。为了恢复这个有意义且有趣的徒步传统，教练正在为今年夏天计划一次远足活动。此外，新队员们强烈要求去一个“刺激”的地方。为了满足他们的愿望，教练找到了一座国家公园并获取了该公园的地图。在这张地图上，有 $n$ 个交叉口（从 $0$ 编号到 $n-1$）由 $m$ 条单向道路连接。这张地图有一个有趣的特点：一旦你离开了现在所处的交叉口，就无法回到这个交叉口。因此，这张地图就是一个典型的有向无环图！

那么，为什么这个地方很刺激呢？因为有些道路被称为“桥”（它们不是真正的桥，而是我们即将定义的特殊道路），它们很危险，因为这些“桥”在我们经过时可能会倒塌。别慌！安全设施充足且坚固，只会对心理产生影响，不会有身体上的危险。尽情玩吧！

远足将从某个起始交叉口 $s$ 开始，并在某个终点交叉口 $t$ 结束。你可以找到从交叉口 $s$ 到 $t$ 的路线。某条道路称为“桥”当且仅当一旦它消失，你就无法找到从起始交叉口到达终点的路线。其他普通道路不是“桥”，所以它们根本不危险。根据游客的经验，“桥”的危险等级等于其长度。

一些恶作剧的人想让这次远足变得更加危险。但等等！一个女孩在哭！什么？一个女孩？终于，北大 ACM 队今年招了一名女生！好吧……“女士优先”是北大 ACM 队的长期政策。男孩和女孩最终达成妥协，决定尽可能保证远足的安全。

国家公园提供了一项“快速”服务。远足者最多可以提前预订两辆公交车，帮助他们避开一些最危险的路线。每辆公交车可以从公园里的任何地方（任何交叉口或道路上的任意点）出发。但公交车是由电力驱动的，因此只能连续行驶不超过 $q$ 米，乘客必须在电力耗尽前下车。简单来说，团队可以选择两条“快速”路线（每条路线可以从任何地方开始并在任何地方结束），但每条路线的长度不得超过 $q$ 米。当团队乘坐公交车时，沿途的危险等级可以忽略不计。

问题简化为找到一条从起点交叉口到终点交叉口的最小危险等级的路线。在途中我们可以乘坐两次公交车使我们的路线更安全。两辆公交车的路线可以从任何地方开始并在任何地方结束，但整个团队应该一次乘坐一辆公交车。禁止个人行动。

输入格式

第一行包含一个整数 $T$（$1 \leq T \leq 10$）——测试用例的数量。

对于每个测试用例： 第一行包含五个整数 $n$、$m$、$s$、$t$ 和 $q$（$1 \leq n \leq 100\,000$, $1 \leq m \leq 200\,000$, $0 \leq s$, $t < n$, $s \neq t$, $1 \leq q \leq 1\,000\,000\,000$），分别表示交叉口的数量、道路的数量、起始交叉口、终点交叉口和单辆公交车可以行驶的最大长度。 接下来的 $m$ 行包含有向无环图中所有道路的信息。每行包含一个三元组 $(u,v,w)$，表示从交叉口 $u$ 到交叉口 $v$ 的道路，长度为 $w$ 米（$1 \leq w \leq 1\,000$）。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最优路线的总危险等级。如果从 $s$ 到 $t$ 没有路线，输出 -1。

输入输出样例 #1

输入 #1

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

1