U410382 有下界的最短路

题目描述

有一张点数为 $n$ ,边数为 $m$ 的有向图,边权为 $w$ 。对于给定的起点和终点,求出其长度不小于 $x$ 的一条最短路。若无解,输出 $-1$ 。

输入格式

第一行有三个整数,分别为 $n,m,x$;\ 接下来 $m$ 行,每行有三个整数 $u,v,w$ ,表示 $u$ 和 $v$ 之间有一条边权为 $w$ 的有向边;\ 最后一行有两个整数,表示起点和终点。

输出格式

输出一个整数,表示长度不小于 $x$ 的最短路的长度。若无解,输出 $-1$ 。

说明/提示

对于所有的数据,$1 \leq n,m \leq 10^5$,数据保证无自环和重边。