题目描述

$Farmer John$ 有若干个农场，编号为 $1, 2, ……$

有 $M$ 条双向通行的道路。每条道路连接两个不同的农场。两个农场间最多有一条道路。

奶牛 $Bessie$ 希望找到一条路线，从农场 $A$ 出发，恰好经过 $N$ 条道路（同一条道路可以重复经过，每经过一次累加一条），到达农场 $B$，并且经过的路程尽可能短。

你能帮助她吗？

输入格式

第一行：四个正整数 $N,M,A,B$

接下来 $M$ 行：每行三个正整数 $w,u,v$ ，表示 $u$ 和 $v$ 之间有一条长度为 $w$ 的道路。

输出格式

一个整数，表示满足条件的最短路的长度。如果找不到满足条件的路径，则输出 -1

样例输入1

4 3 1 3
1 2 1
2 3 2
3 4 3

样例输出1

5

样例输入2

4 3 1 2
1 2 1
2 3 2
3 4 3

样例输出2

-1

数据范围

$100\%$的数据：$2 ≤ N ≤ 1,000,000$， $2 ≤ M ≤ 100$， $1 ≤ u, v, w ≤ 1,000$