#P1629. 邮递员送信

邮递员送信

题目描述

有一个邮递员要送东西,邮局在节点 11。他总共要送 n1n-1 样东西,其目的地分别是节点 22 到节点 nn。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 mm 条道路。这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。求送完这 n1n-1 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数,nnmm,表示城市的节点数量和道路数量。

第二行到第 (m+1)(m+1) 行,每行三个整数,u,v,wu,v,w,表示从 uuvv 有一条通过时间为 ww 的道路。

输出格式

输出仅一行,包含一个整数,为最少需要的时间。

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2
83

提示

对于 30%30\% 的数据,1n2001 \leq n \leq 200

对于 100%100\% 的数据,1n1031 \leq n \leq 10^31m1051 \leq m \leq 10^51u,vn1\leq u,v \leq n1w1041 \leq w \leq 10^4,输入保证任意两点都能互相到达。