P2886 [USACO07NOV] Cow Relays G

为了完成他们的体能训练计划，$N$（$2 \le N \le 10^6$）头奶牛决定利用牧场中的 $T$（$2 \le T \le 100$）条牛径进行一场接力赛跑。 每条牛径连接两个不同的交叉路口，编号满足 $1 \le I_{1,i} \le 1000$，$1 \le I_{2,i} \le 1000$，每个交叉路口至少是两条牛径的端点。奶牛们知道每条牛径的长度 $\text{length}_i$（$1 \le \text{length}_i \le 1000$）、它所连接的两个交叉路口，并且没有两条不同的牛径直接连接同一对交叉路口。这些牛径在数学上构成一个图。 为了进行接力赛跑，$N$ 头奶牛被放置在不同的交叉路口（有些路口可能有多头奶牛）。它们必须被正确放置，以便能够一头接一头地传递接力棒，并最终到达终点位置。 请编写程序帮助安排奶牛的位置。求出从起点 $S$ 到终点 $E$，恰好经过 $N$ 条牛径的最短路径长度。

第一行四个正整数 $N,T,S,E$ ，意义如题面所示。 接下来 $T$ 行每行三个正整数 $w,u,v$ ，分别表示路径的长度，起点和终点。

一行一个整数表示图中从 $S$ 到 $E$ 经过 $N$ 条边的最短路长度。

对于所有的数据，保证 $1\le N\le 10^6$，$2\le T\le 100$。 所有的边保证 $1\le u,v\le 1000$，$1\le w\le 1000$ 且不存在重边，自环。 所有的顶点保证至少连接两条边。