X的浪漫表白

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

经过了一系列的努力,X终于要追到学妹了,为了表示程序员不是程序猿,所以X想要准备一个浪漫的表白,X准备想将自己的宿舍,学妹的宿舍,还有四体用蜡烛连接起来,在四体X准备了最漂亮的烟花。但是X穷啊,买不起那么多蜡烛,为了用更少的蜡烛,所以他想要知道连接这三个地点的最短的距离。我们大家表现的时候到了,帮助X解决一下问题吧。

学校有很多建筑物啊,有一些道路将这些建筑物连接起来了,通过这些道路可以将任意两个建筑连接起来。已知这些道路的长度,那么我们找出连接X的宿舍,学妹的宿舍,四体的最短路径吧。

Input

 

第一行输入两个整数nm3 <= n <= 100 , 3 <= m <= n*(n-1)/2 )。n为建筑物数,建筑物标号为1m为道路数。X的宿舍标号为1,学妹的宿舍标号为2,四体的标号为3

之后m行每行三个整数 u v w 表示存在一条长度为w的道路,连接起uv两个建筑物。( 1 <= u,v <= n && w < 100)

Output

 

输出一个整数,为连接这三个点的最短距离。

Sample Input

4 4
1 2 3
1 3 2
2 4 1
3 4 1

Sample Output

4

Hint

 

Source

winddreams