Farmer John 拥有 n 块田地，分别编号 1,2,\dots,n ，在田地之间有 m 条双向道路，每条道路有一定的长度。
现问：若从 1 走到 n 再走回 1 ，期间不经过重复的道路，经过的路径长度之和最短是多少？
保证一定存在至少一条满足要求的路径。
输入的第一行是两个正整数 n 和 m ，分别表示田地的块数和道路的条数。
接下来 m 行，每行有三个正整数 s 、 t 和 v ，分别表示一条道路的两个端点和这条道路的长度。
一行一个整数，表示最短的距离和。
4 5 1 2 1 2 3 1 3 4 1 1 3 2 2 4 2
6
对于全部数据， 1\leq n \leq 1000 ， 1 \leq m \leq 10000 ， 1 \leq s,t \leq n ， 1 \leq v \leq 35000 。