题目描述

在神奇的 oi 国度，有 $\red n$ 个城市 $\red m$ 条双向道路，每条道路连接了两个不同的城市

寒假 到了，小 S 决定出门旅游一趟

因为以往跟团旅游多了，这次小 S 决定自驾游

对于自驾 游，小 S 最关心的自然是燃油的耗费，为了省钱，小 S 请你帮他找一条最短的路

输入格式

第一行两个整数 $\red n$,$\red m$，表示有 $\red n$ 个城市和$\red m$ 条双向道路

城市从 $\red {1..n}$ 编号

接下来 $\red m$ 行，每行三个正整数 $\red a$,$\red b$,$\red c$，表示 $\red a$ 和 $\red b$ 之间有一条长为 $\red c$ 的双向道路

$\red a$,$\red b$ 不 相同，且 $\red c$ 不超过 $\red {1000}$

注意:两个城市之间可能会有多条双向道路

接下来一行两个整数，$\red s$,$\red t$，表示小 S 本次旅行的出发地和目的地

$\red s$,$\red t$ 不相同

输出格式

仅一行一个整数，表示最短的距离

如果不能到达，请输出$\red {-1}$

样例

输入样例

3 3
1 2 1
1 3 3
2 3 1
1 3

输出样例

2

提示

样例解释:

$\red {1->2->3}$ 即是最优解

数据范围:

对于 $\red {30\%}$的数据，$\red {n<=100,m<=1000}$

对于 $\red {100\%}$的数据，$\red {n<=2000,m<=100000}$