2173: war

 木叶忍者村--------------拥有精锐忍者军团的最强忍者村在村子的村长[火影]的带领下，全体村民团结的力量与许多优秀的忍者，让木叶忍者村变得非常繁荣，而且这也让村民有了在其他国家的民众身上不太容易看到的爱国心。木叶忍者村的忍者们虽然活在严苛的忍者世界中，但是却都效忠村子，而且还把村子里的人们当成自己的家人般喜爱与保护着，而在他国可能会受到迫害的拥有奇异能力之人，在这个村子也不会受到差别待遇。这种自由的风俗造就了这个村子的繁荣。
    话说木叶要和死神开战了，他们打的那是天昏地暗，鬼哭狼嚎，地动山摇，炊烟袅袅升起，这一仗造成人员大面积死亡，只剩余<=3万人还活在战场上，为了了解大战实况，你只身一人进入大战阵营，你会选择一条简单的路径，不过由于大战，好多路都封死了，在完好的路中也有危险系数，你当然要选危险小的走，不过，为了了解全部实况，你必须拜访所有的人。

  n m (n,人数 m,路数) ：（注意，两点间路不止一条）
    x y z (m 行，x,y人，z危险系数z>=0)
    （注意：没有出现的就表示不通）

最小危险系数

4 7
1 2 477
2 3 267
3 4 0
2 1 137
2 1 564
3 1 408
3 4 152

404