LG#P1629. 邮递员送信
邮递员送信
题目描述
有一个邮递员,邮局位于顶点 。城市有 个顶点、 条单向道路,第 条道路从 指向 ,通行时间为 。
邮递员需要分别向顶点 各送一件物品。每次只能带一件物品,每次送达后都必须返回邮局,最后也必须位于邮局。每条道路可以重复经过。
保证任意两个顶点之间都能互相到达。求完成全部投递所需的最少总时间。
输入格式
第一行输入两个整数 $n,m\left(1\leqq n\leqq10^3;\ 1\leqq m\leqq10^5\right)$。
此后 行,每行输入三个整数 $u_i,v_i,w_i\left(1\leqq u_i,v_i\leqq n;\ 1\leqq w_i\leqq10^4\right)$,代表一条单向道路。
允许重边,保证图强连通,即任意两点可以沿有向道路互相到达。
输出格式
输出一个整数,代表最少总时间。若只有邮局一个顶点,则无需投递,输出 。
测试样例
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 解释
分别投递到顶点 时,最短去程与返程总时间依次为 ,相加得到 。各次投递必须回邮局,不能把不同目的地串成一次配送。
2 2
1 2 1
2 1 10
11
子任务
对于 的数据,;其余数据无额外限制。