题目描述

魔法世界有$\red{N(N<100)}$个城市,某些城市之间有公路连接,任意两个城市可以通过公 路直接或者间接到达.并且任意有公路连接的两个场所之间.来回使用的交通工具不一样。 所以费用也不一样,现从$\red{A}$场所出发去$\red{B}$场所,最后再返回$\red{A}$场所,请设计一条来回最小交 通费用的线路。

输入格式

第一行有两个数$\red{N,M(N}$为场所个数,$\red{M}$为场所间交通路线图$\red{)}$

第二行至第$\red{M+1}$行分别有三个数字,前两个为场所编号,第三个为它们的交通费用。

第$\red{M+2}$行有两个数字,为两个求解的场所编号.

输出格式

一个整数，最小交通费。

样例

输入样例

3 5
1 2 4
2 1 6
1 3 11
3 1 3
2 3 2
1 2

输出样例

9