LG#P1629. 邮递员送信

邮递员送信

题目描述

\hspace{15pt}有一个邮递员,邮局位于顶点 11。城市有 nn 个顶点、mm 条单向道路,第 ii 条道路从 uiu_i 指向 viv_i,通行时间为 wiw_i。

\hspace{15pt}邮递员需要分别向顶点 2∼n2\sim n 各送一件物品。每次只能带一件物品,每次送达后都必须返回邮局,最后也必须位于邮局。每条道路可以重复经过。

\hspace{15pt}保证任意两个顶点之间都能互相到达。求完成全部投递所需的最少总时间。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m\left(1\leqq n\leqq10^3;\ 1\leqq m\leqq10^5\right)$。

\hspace{15pt}此后 mm 行,每行输入三个整数 $u_i,v_i,w_i\left(1\leqq u_i,v_i\leqq n;\ 1\leqq w_i\leqq10^4\right)$,代表一条单向道路。

\hspace{15pt}允许重边,保证图强连通,即任意两点可以沿有向道路互相到达。

输出格式

\hspace{15pt}输出一个整数,代表最少总时间。若只有邮局一个顶点,则无需投递,输出 00。

测试样例

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

样例 1 解释

\hspace{15pt}分别投递到顶点 2,3,4,52,3,4,5 时,最短去程与返程总时间依次为 29,24,15,1529,24,15,15,相加得到 8383。各次投递必须回邮局,不能把不同目的地串成一次配送。

2 2
1 2 1
2 1 10
11

子任务

\hspace{15pt}对于 30%30\% 的数据,n≦200n\leqq200;其余数据无额外限制。