9310 - 海军上将

Michiel Adriaenszoon de Ruyter是荷兰历史上最著名的参加了17世纪英荷战争的海军上将。他亲自指挥旗舰，并在海战中向盟军军舰发出命令。

在De Ruyter的时代，图论刚刚发明，这位海军上将将其应用于在策划海战的作战计划。海上航路点由顶点表示，以及从一个航路点到另一个航路点的一条航路表示为一条有向边。给定任何两个航路点W1和W2之间最多有一个通道W1→ W2。在每个定向边上航行沿途会遭遇敌人的袭击，不过我们可以回击来击沉沿途遇到的敌舰。

De Ruyter最成功的战术之一是De Ruyter的机动。两艘军舰从同一个航路点出发，分头战斗，穿过敌方舰队，加入在目的汇合航路点再次汇合。演习规定两艘军舰分离路线，意味着它们不能访问同一个航路点（除了起点和终点），或者在战斗中使用相同的通道。

海军上将Michiel Adriaenszoon de Ruyter不喜欢浪费金钱；我们需要计划发射尽可能少的昂贵炮弹的路线。

上图为两艘船的航行路线。两艘船（“红色”和“蓝色”）从出发点（1）移动到集合点（6）。红船的航线是1→ 3→ 6（沿途发射33个炮弹）；蓝船的航线是1→ 2→ 5→ 4→ 6（沿途发射了53个炮弹）。演习期间总共发射了86枚炮弹。

除了起点和终点，两艘船都不会访问相同的任何顶点或边。

对于每个测试用例，输入包括：

• •第一行包含两个整数v（3≤v≤1000）和e（3≤e≤10000）的分别表示航路点的个数(1到v编号)和航道的数量。
  
• •接下来是e行：对于每一段，一行包含三个整数：
  1.a_i（1≤a_i≤v），一条航道的起点编号；
  2.b_i（1≤b_i≤v , a_i \not = b_i），航道的终点编号，所有航道都是单向的不可返回（即有向边）；
  3.c_i（1≤c_i≤100），经过航道时需要耗费的弹药数量。
  
  起始航路点为1，目的航路点为v。题目保证总是至少有两个符合题意的从航路点1到航路点v的路线。
  

UVA1658