题目背景

这是 $CSP-J$ 模拟赛的 $T3$ 。

题目描述

$Alice$ 有一个 $n$ 个点 $m$ 条边的无向正权图 $G$ ，保证图是联通的。

$Alice$ 想要构造一个新的无向正权图 $G'$ ，使得新图中两两点之间的最短路的长度与原图一样，并且边权值之和尽可能的小。

请求出边权和的最小值。

输入格式

输入多行。

第一行两个整数 $n,m$​ ，表示点的个数和边的条数。

接下来 $m$ 行，每行 $3$ 个整数 $u_i,v_i,w_i$ ，表示有一条连接 $u_i$ 和 $v_i$ ，边权为 $w_i$ 的边。

输出格式

输出一行。

一个整数表示新图$G'$的最小的边权和。

样例 #1

样例输入 #1

4 4
1 2 1
2 3 1
3 4 1
4 1 3

样例输出 #1

3

样例 #2

样例输入 #2

6 7
1 2 2
1 3 7
2 4 2
2 5 2
4 6 8
6 3 7
6 2 3

样例输出 #2

23

提示

数据范围】：

对于前 $20\%$ 的数据满足 $n\le 5 ,m \le 10,w_i \le 5$ 。

对于另外 $20\%$ 的数据满足 $n \le 10,m \le 20,w_i \le 100$ 。

对于另外 $30\%$ 的数据满足 $m=n-1$ 。

对于所有数据，满足 $1\le n\leq 300,n-1 \le m \le 1000,1 \le w_i \le 10^9,u_i \neq v_i$ 。