0x60图论（0x61 最短路）例题6：牛站

P2886 [USACO07NOV] Cow Relays G

题目描述

给定一张 $T$ 条边的无向连通图，求从 $S$ 到 $E$ 经过 $N$ 条边的最短路长度（若 $N$ 比 $T$ 大，是因为反复经过)。

输入格式

第一行四个正整数 $N,T,S,E$ ，意义如题面所示。

接下来 $T$ 行每行三个正整数 $w,u,v$ ，分别表示路径的长度，起点和终点。

输出格式

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

输入输出样例 #1

输入 #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

说明/提示

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

所有的边保证 $1\le u,v\le 1000$，$1\le w\le 1000$。