L. [L2-4] 春节路线

春节返乡高峰期间，你要从城市 驾车前往城市 。道路构成一张 个点、 条双向道路的图，每条道路都有一个正整数通行耗时。

由于车流量激增，自信的你预测：司机会优先选择“足够快”的路线，从而造成某些路段拥堵。定义：

• 设在原图中从 到 的最短通行时间为 （若不可达则视为无穷大）；
• 给定参数 ，任何总耗时 不超过 的从 到 的路线都会被大量司机选择并拥堵；
• 为了完全避开这些拥堵路段，你选择的路线必须满足：
  你路线中的每一条道路，都不能以相同的经过方向出现在任何一条总耗时 的 路线中。
  （也就是说，只要某条道路在某条“足够快”的路线里出现过并且经过这条路径的方向一致，这条路线就禁止使用。）

在满足上述避堵规则的前提下，请求出你仍然能够到达城市 时的最短通行时间；若无法到达，则输出 。

第一行三个整数 。

接下来 行，每行三个整数 ，表示两条有向边 和 ，通行耗时均为 。

输出一个整数：

若存在满足避堵规则的路线，输出其最短通行时间；

否则输出 。

样例输入 1

4 5 0
1 2 1
2 3 1
3 4 1
1 3 3
2 4 3

样例输出 1

7

样例输入 2

10 20 2
1 4 6
5 7 7
3 6 6
3 5 12
1 5 7
4 7 12
8 10 7
8 9 8
5 10 12
5 6 9
3 9 10
5 8 12
4 5 12
9 10 6
1 6 3
6 8 8
4 6 8
1 10 6
6 7 11
4 10 4

样例输出 2

10

样例解释 1

最短路为 ，被限制，但还可以走 ，时长为 7。

因为 只认为 堵车，但 不堵。

且