J19 习题-3 奶牛小路

题目描述

对于他们的体能计划，$N$ 头牛决定用 $T$ 条奶牛小路走遍牧场。

每条小路连接两个不同的交叉口 $I_{1i}$ 和 $I_{2i}$，每一个都是至少两条路径的终端。奶牛知道每条小路的长度 $length_i$，这条小路连接的两个路口，他们知道没有两个路口是由两条不同的小路直接连接的。这些轨迹形成了数学上称为图形的结构。

为了进行接力，$N$ 头牛在不同的交叉路口（有些交叉路口可能有多头牛）进行定位。他们必须正确定位，这样才能一头牛一头牛地接过指挥棒，最终到达正确的终点。

编写一个程序来帮助奶牛定位。找到连接起点交叉口（$S$）和终点交叉口（$E$）的最短路径，并精确地穿过 $N$ 条奶牛小路。

输入格式

第 $1$ 行：四个空格分隔的整数：$N$、$T$、$S$ 和 $E$。

第$2..T+1$行：第 $i+1$ 行用三个空格分隔的整数描述小路 $i$：$length_i$、$I_{1i}$ 和 $I_{2i}$。

输出格式

第 $1$ 行：一个整数，它是从交叉点 $S$ 到交叉点 $E$ 的最短距离，正好穿过 $N$ 条奶牛小路。

样例输入

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

样例输出

10

数据范围

对于$100\%$的数据：$2 \le N \le 1000000$，$2 \le T \le 100$，$1 \le length_i \le 1000$， $1\le I_{1i},I_{2i}\le 1,000$。