Michiel Adriaenszoon de Ruyter 是荷兰历史上最著名的海军上将，他在 17 世纪的英荷战争中发挥了重要作用。De Ruyter 曾亲自指挥旗舰，并在海战中向盟军战舰下达指令。

在 De Ruyter 的时代，图论刚刚被发明出来，这位上将利用图论在规划海战时取得了巨大优势。海上的航点被表示为顶点，从一个航点到另一个航点的可能通道被表示为有向边。对于任意两个航点 $W_1$ 和 $W_2$，最多存在一条从 $W_1$ 到 $W_2$ 的通道。每条有向边都标有为了安全通过该航线并击沉沿途敌舰所需发射的炮弹数量。

De Ruyter 最成功的战术之一是“De Ruyter 机动”。在这种战术中，两艘战舰从同一个航点出发，分头穿过敌方舰队，最后在目的地航点汇合。该机动要求两艘战舰采取不相交的路线，这意味着它们除了起点和终点外，不能访问相同的航点，也不能在战斗中使用相同的通道。

作为荷兰人，De Ruyter 上将不喜欢浪费金钱；在 17 世纪的海战中，这意味着要尽可能少地发射昂贵的炮弹。

图 1：De Ruyter 战术的一个具体实例，可视化为图。两艘船（“红色”和“蓝色”）从共同的起点 (1) 移动到共同的终点 (6)。红色船的路线是 $1 \to 3 \to 6$（沿途发射 33 枚炮弹）；蓝色船的路线是 $1 \to 2 \to 5 \to 4 \to 6$（沿途发射 53 枚炮弹）。在机动过程中总共发射了 86 枚炮弹。除了起点和终点外，没有顶点或边被两艘船同时访问。

输入格式

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

• 一行包含两个整数 $v$ ($3 \le v \le 1000$) 和 $e$ ($3 \le e \le 10000$)，分别表示航点和通道的数量。
• 接下来有 $e$ 行：每条通道一行，包含三个整数：
  1. $a_i$ ($1 \le a_i \le v$)，通道的起点，由一个航点表示；
  2. $b_i$ ($1 \le b_i \le v$) 且 ($a_i \neq b_i$)，通道的终点，由一个航点表示。所有通道均为有向通道；
  3. $c_i$ ($1 \le c_i \le 100$)，沿该通道航行时发射的炮弹数量。

起始航点为 1，目的地航点为 $v$。从航点 1 到航点 $v$ 始终至少存在两条不相交的路线。

输出格式

对于每个测试用例，输出一个正整数：两艘船到达目的地航点时发射的炮弹总数之和的最小值。

样例

输入 1

6 11
1 2 23
1 3 12
1 4 99
2 5 17
2 6 73
3 5 3
3 6 21
4 6 8
5 2 33
5 4 5
6 5 20

输出 1

86