问题描述

当FJ的朋友们来农场拜访时，他喜欢带他们参观。他的农场由$N$（$1 ≤ N ≤ 1000$）块田地组成，编号为1到$N$，其中1号田地是他的房子，$N$号田地是大谷仓。共有$M$（$1 ≤ M ≤ 10000$）条路径以不同方式连接这些田地。每条路径连接两块不同的田地，并且具有一个非零的长度（小于35,000）。

为了以最佳方式展示他的农场，他会进行一次游览：从房子出发，可能会经过一些田地，最终到达谷仓。之后，他再返回房子（可能经过一些田地）。

他希望这次游览尽可能短，但不想重复走过任何一条路径。请计算可能的最短游览路线。FJ确信对于任何给定的农场都存在这样的游览路线。

输入格式

• 第一行：两个用空格分隔的整数$N$和$M$。
• 接下来的$M$行：每行包含三个用空格分隔的整数，表示一条路径的起始田地、结束田地和路径长度。

输出格式

• 一行，包含最短游览路线的长度。

示例输入

4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2

示例输出

6

来源

USACO 2003年2月Green组