题目来源：http://noi.openjudge.cn/ch0405/3368/
重点词汇：
era： n.时代
commander：n.统帅，指挥者
strategist ：n.谋士
eligible：adj.可以选的，合格的
generals：n.将军
bi-directed roads：n.双向道
hire ：v.雇佣
suppose：v.假设
3368:Sanguo
三国
- 总时间限制:
- 3000ms
- 内存限制:
- 65536kB
- 描述
-
After East Han dynasty, China was divided into several states. Wei, Wu, and Shu are the greatest three states among them. This was the era of Sanguo. During this period, wars frequently happened between states. Zhuge Liang, the commander and strategist of Shu, wanted to enlarge Shu's power. He was considering conquering N cities. However, these cities must be defeated in a specified order. City-X could be defeated only after City-1, City-2, City-3 ... City-(X-1) had been defeated. However, passing through the cities that had not been defeated was eligible. Zhuge wanted to use three generals, Guan Yu, Zhang Fei, and Zhao yun, each of whom should lead an army. The three armies, started from Yizhou, which was numbered with City-0. After conquered all the N cities (each cities must be conquered at least by one army), they had to return to Yizhou.
东汉末年，中国被划分为多个国家。魏，吴，蜀则是其中最大的三个国家。这是三国的时代，在这个时期，各国间的战争频繁地发生。诸葛亮作为蜀国的统帅和谋士（军师），想要扩大蜀国的*，所有他考虑占领n个城市。然而，这些城市必须按照特定的顺序被打败。城市-X只能在城市--1，城市--2，城市--3······城市--（X-1）被打败之后才能被打败。然而，通过没有被打败的城市是有资格的。诸葛亮想用三位将军，关羽，张飞，和赵云，每一个将军应该领导一个军队。这三支军队从城市--0 益州开始出发。在占领所有的N 城市之后（每一个城市至少需要用一支军队来占领），他们都必须要返回到益州。
The N cities and Yizhou were connected by M bi-directed roads. To travel from city to city was a very boring and expensive thing. So Zhuge wanted to minimize the total length of the three armies' traveling. You were hired to help him to compute the minimum total length of the traveling.
N个城市和益州由M条双向道路相连。 从一个城市到另一个城市的旅程是一件非常无聊和昂贵的事情。 所以诸葛想尽量减少三军行军的总长度。 你被雇来帮助他计算行军的最短总长度。
- 输入
-
Line1: two integers N and M. N is the number of cities Zhuge wanted to conquer, and M is the number of roads between the N + 1 cities.
Line2...Line(M+1): each line contain 3 integers, X, Y, Len, indicating a road between City-X and City-Y, with the length of Len.
You can suppose that all the N + 1 cities are connected.
N ≤ 500, M ≤ 20000, Len ≤ 1000行列1：两个整数N 和 M。N表示诸葛亮想要占领的城市数量，M表示N+1个城市之间道路的总数量。
行列2·····行列（M+1）：每一行包含三个整数，X，Y，Len，表示城市X 到城市 Y的长度 Len。
你可以假设N+1个城市是连接的。
N<=500,M<=20000,Len<=1000
- 输出
-
Line1: an integer, which is the minimum total length of the three armies' traveling.
行列1：一个整数，表示三军行军的最短总路程。
- 样例输入
-
5 15 5 5 48 1 4 658 4 0 843 1 4 41 1 4 330 5 2 864 4 2 115 4 0 303 2 3 685 0 0 879 1 5 649 2 4 942 4 0 379 5 2 769 5 1 856
- 样例输出
-
3668