该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

在神奇的 oi 国度，有 n 个城市 m 条双向道路，每条道路连接了两个不同的城市。寒假到了，小 S 决定出门旅游一趟。因为以往跟团旅游多了，这次小 S 决定自驾游。对于自驾游，小 S 最关心的自然是燃油的耗费，为了省钱，小 S 请你帮他找一条最短的路。

Format

Input

第一行两个整数 n,m，表示有 n 个城市和 m 条双向道路。城市从 1..n 编号。

接下来 m 行，每行三个正整数 a,b,c，表示 a 和 b 之间有一条长为 c 的双向道路。a,b 不 相同，且 c 不超过 1000。

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

接下来一行两个整数，s,t，表示小 S 本次旅行的出发地和目的地。s,t 不相同。

Output

仅一行一个整数，表示最短的距离。如果不能到达，请输出-1。

Samples

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

2

Limitation

【样例解释】 1-->2-->3 即是最优解。

【数据范围】

对于 30%的数据，n<=100,m<=1000

对于 100%的数据，n<=2000,m<=100000