Source : 信息学奥赛一本通训练指导教程
Description

  给定 MM 条边,NN 个点的带权无向图。求 11NN 的最短路。

Input

  第一行:N,M(N100000M500000)N,M(N≤100000,M≤500000)
  接下来 MM33 个正整数:ai,bi,cia_i,b_i,c_i表示 ai,bia_i,b_i 之间有一条长度为 cic_i 的路,ci1000c_i≤1000

Output

  一个整数,表示 11NN 的最短距离。

Sample Input
4 4
1 2 1
2 3 1
3 4 1
2 4 1
Sample Output
2