最小交通费用问题

描述

某游乐城内有N个活动场所，某些活动场所之间有公路连接，任意两个场所可以通过公路直接或者间接到达，并且任意有公路连接的两个场所之间，来回使用的交通工具不一样，所以费用也不一样，琪儿和琳琳在A场所时，琳琳有点累，想休息一下，此时琪儿只能单独去B场所，请设计一条A到B来回最小交通费用的线路。RuQ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入

第一行有两个数N，M（N＜100，为场所个数，M用于描述场所间交通路线图）。 第二行至第M＋1行分别有三个数字，前两个为场所编号，第三个为它们的交通费用。 第M＋2行有两个数字，为两个求解的场所编号。RuQ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出

一个整数（最小交通费）。RuQ100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

样例

输入

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

输出

9