#1900. 沉石鱼惊旋

沉石鱼惊旋

题目描述

小 C 有一张 nn 个点 mm 条边的简单无向带权连通图 GG。

现在你可以进行 nn 次操作,每次操作如下:

选择一个仍未被删除的点 uu,然后删除点 uu 和当前与 uu 相连的所有边(即其中一个端点是 uu 的边)。假设本次删除的边的边权分别是 w1,w2,…wkw_1, w_2,\dots w_k,则本次操作的代价是 k×(w1+w2+⋯+wk)k\times (w_1+w_2+\dots+w_k)。

你的总代价是这 nn 次操作的代价和。

显然 nn 次操作后,所有的边和点都将被删除。现在小 C 想知道,将图中所有点和边都删除(即把图删空)的最小总代价是多少。当然,在过程中你不需要保证图每次操作后仍然连通。

天寒翠袖薄,日暮倚修竹。

输入格式

第一行,两个整数 n,mn,m。

接下来的 mm 行,每行 33 个整数 u,v,wu,v,w,表示 uu 和 vv 之间有一条边权为 ww 的边。

输出格式

一行,一个整数,表示删空图 GG 的最小代价。

样例

6 8
1 3 10
1 5 20
1 6 30
2 5 10
2 6 20
3 4 30
3 5 10
5 6 20
240

题目来源:洛谷 P12593