题目描述

农场中有 $T$ 条道路连接着各个路口。$N$ 头奶牛要参加接力赛，从起点 $S$ 跑到终点 $E$，每头奶牛跑一条道路。请找出一条恰好经过 $N$ 条道路的最短路径。

输入格式

第一行四个整数 $N$、$M$、$S$、$E$，分别表示奶牛数量（即路径长度）、道路数量、起点和终点。

接下来 $M$ 行，每行三个整数 $w$、$u$、$v$，表示一条长度为 $w$ 连接路口 $u$ 和 $v$ 的双向道路。

输出格式

一行一个整数，表示最短路径长度。

样例

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

10

提示

$2 \le N \le 10^6$，$2 \le T \le 100$，$1 \le u, v \le 1000$，$1 \le w \le 1000$