题目描述

为了完成他们的体能训练计划，$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$ 条边的最短路长度。

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

10

提示

对于所有的数据，保证 $1\le N\le 10^6$，$2\le T\le 100$。

所有的边保证 $1\le u,v\le 1000$，$1\le w\le 1000$ 且不存在重边，自环。

所有的顶点保证至少连接两条边。