说明

众所周知，火火火学长对软件园内部的路十分不熟悉，尤其是在晚上。

这天傍晚，正在食堂嗦面的他突然被通知要去软件园某教室找几位学长办事。他不太清楚这路该怎么走，这极大地困扰到了他，因为火火火学长是个爱学习的人，他想尽早办完事回到宿舍开始刷题。

于是火火火学长找到了你，希望你能帮他规划一条最快到达几位学长所在教室的路，让他能够早点办完事然后回宿舍学习。

输入格式

第一行是三个整数，分别代表食堂、学长们所在教室、宿舍的位置序号。

第二行是两个整数n（3<=n<=2000）、m（2<=m<=10000），分别代表位置序号总数和路径总数。

接下来是m行，每行三个整数x（1<=x<=n）、y（1<=y<=n）、v（1<=v<=1000），表示从x到y需要v时间。

数据保证食堂、学长们所在教室、宿舍能走通。

输出格式

一个整数，即火火火学长从食堂出发并完成任务后回到宿舍所需的最少时间。

样例

1 3 4
5 8
1 2 3
1 4 1
2 4 1
5 4 9
1 5 7
5 3 5
1 3 2
2 5 2

5

样例

3 1 2
4 4
1 3 9
1 2 21
3 4 1
2 4 3

22