为锻炼身体，$N$ 头牛（$(2 \le N \le 1,000,000)$）决定利用牧场 $T$ 条路（$(2 \le T \le 100)$）跑接力。

每路连接两个不同路口（$(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$），每路口至少连两条路。已知每路长度 $length_i$（$(1 \le length_{i} \le 1,000)$）和两端；没有两路直接连同一对路口。道路构成数学中的图。

$N$ 头牛站不同路口，同一口可有多头。必须合理安排，逐牛传棒并到正确终点。

编程帮助安排，求起点 $S$ 到终点 $E$ 恰经过 $N$ 条路的最短路径。

输入格式

• 第 $1$ 行：空格分隔整数 $N$、$T$、$S$、$E$。

• 第 $2..T+1$ 行：第 $i+1$ 行给路 $i$ 的三个空格分隔整数 $length_i$、$I1_i$、$I2_i$。

输出格式

• 第 $1$ 行：从 $S$ 到 $E$ 恰过 $N$ 条路的最短距离，一个整数。

样例

输入格式 1

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

输出格式 1

10

出题人：Erik Bernhardsson，2003