乌鸦坐飞机

Time Limit: 15000 ms Memory Limit: 65536 KiB

Problem Description

传说中的乌鸦(阿福)今天准备去一个神秘的地方进行一些不 (xie) 为 (e) 人 (zhi) 知 (ji) 的 py 交易。~~(喂!,如果是乌鸦的话为什么还要坐飞机啊)~~只不过这货已经是懒癌晚期了,她决定放出她的大招,乌鸦坐飞机!

 

4049

 

阿福看到(世界?)地图上有 $n$ 个城市,城市之间有 $m$ 条道路,每条道路花费的时间不同。现在阿福想要从当前的 $s$ 城市出发到达 $t$ 城市,进行交易,如今阿福已经是失去理性的英灵了,你能帮帮她找出花费时间最少的道路么?

Input

第一行输入两个以空格分隔的整数 $n$, $m$。表示地图上一共有 $n$ 个城市,$m$ 条边。

$(2 \leqslant n \leqslant 1000, 0 \leqslant m \leqslant 100000)$

接下来输入 $m$ 行,每行 $3$ 个整数 $u$, $v$, $w$ 表示 $u$ 和 $v$ 之间有一条道路,花费的时间为 $w$。

$(1 \leqslant u, v \leqslant n, 0 \leqslant w \leqslant 1000)$

接下来一行输入两个以空格分隔的整数 $s$, $t$。表示阿福当前在 $s$ 城市,准备去往 $t$ 城市。

$(1 \leqslant s, t \leqslant n)$

Output

如果阿福可以从 $s$ 到达 $t$,则输出需要花费的最少时间。否则输出 $-1$。

Sample Input

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

Sample Output

3

Hint

Source

【2016级ACM暑假集训 结训赛(数据结构组)】UMR