SP3405 SAMER08A - Almost Shortest Path

寻找从起点到终点的最短路径是一个已经广为人知的问题，现在甚至已经成为我们日常生活的一部分，因为最短路径程序已经非常普及。大多数人都非常喜欢这些应用程序，因为它们让生活变得更方便。然而，由于几乎每个人都能使用 GPS 导航设备来计算最短路径，导致形成最短路径的大多数路线因交通拥堵而变得缓慢。因为大多数人试图遵循同一条路径，所以再遵循这些方向已经不值得了。 考虑到这一点，你的老板要求你开发一个只有他能访问的新应用程序，从而在他有会议或紧急事件时节省时间。他要求程序不仅要回答最短路径，还要回答次短路径。他定义的次短路径是从起点到终点的最短路径，但这条路径上的任意一段都不能属于任何从起点到终点的最短路径。 例如，假设下图表示给定的地图，圆圈表示地点，线条表示单向直接路线，长度已标出。起点标记为 S，终点标记为 D。粗线属于一条最短路径（在这种情况下有两条最短路径，每条总长度为 4）。因此，次短路径将由虚线表示（总长度为 5），因为没有一段路线属于任何最短路径。注意可能存在多个可能的答案，例如如果长度为 3 的路线变为长度 1。也可能不存在答案。 

输入包含多组测试数据。每组测试数据的第一行包含两个整数 $N$ 和 $M$（$2 \leq N \leq 500$，$1 \leq M \leq 10000$）。第二行包含两个整数 $S$ 和 $D$，分别表示起点和终点（$S \neq D$；$0 \leq S, D < N$）。 接下来的 $M$ 行，每行包含三个整数 $U$、$V$ 和 $P$（$U \neq V$；$0 \leq U, V < N$；$1 \leq P \leq 1000$），表示从点 $U$ 到点 $V$ 有一条距离为 $P$ 的单向路线。从一个给定点 $U$ 到另一个给定点 $V$ 最多只有一条路线，但请注意，从 $U$ 到 $V$ 存在一条路线并不意味着从 $V$ 到 $U$ 也存在一条路线，即使存在这样的路线，其长度也可能不同。输入以一行仅包含两个零的行结束。

对于输入中的每组测试数据，你的程序必须输出一行，如果无法满足要求则输出 -1，否则输出找到的次短路径的长度。