#P2126. Mzc家中的男家丁

Mzc家中的男家丁

题目背景

mzc 与 djn 的…还没有众人皆知,所以我们要来宣传一下。

题目描述

mzc 家很有钱(开玩笑),他家有 nn 个男家丁,现在 mzc 要将她们全都聚集起来(干什么就不知道了)。现在知道 mzc 与男家丁们互相之间通信的时间,请算出把他们每个人叫到需要的总时间(要重复的哦)。保证能把他们每个人叫到。

输入格式

第一行有一个数 nn,表示有 nn 个男家丁。第二行一个数 mm 表示有 mm 条通信路线。之后 mm 行,每行三个数 ai,bi,cia_i,b_i,c_i,表示第 aia_i个男家丁(或 mzx)和第 bib_i 个男家丁(或 mzc)通信需要时间(双向)。ai(bi)=0a_i\left(\text{或}b_i\right)=0 表示 mzc。

输出格式

一行,一个数 sumsum,表示把他们每个人叫到需要的总时间。

5
12
0 2 15
2 3 20
3 5 13
1 3 29
0 1 30
2 4 21
0 3 23
5 1 48
0 4 17
0 5 27
1 2 43
2 5 41

94

提示

n2300,m4×105n\leq2300,m\leq4\times10^5