题目描述

传智专修学院里有 $n$ 栋教学楼，有 $m$ 条双向通行道路连接这些教学楼，不存在重边和自环。每条道路都有一定的长度，而且所有教学楼之间都可以直接或者间接地通过道路到达。我们可以很容易地求出这些教学楼之间的最短路。

为了使交通更为顺畅，校方决定在两个教学楼里增设一对传送门。传送门可以将这对教学楼的距离直接缩短为 $0$。利用传送门，某些教学楼之间的最短路距离就变短了。

由于预算有限，学校里只能安装一对传送门。但是校长希望尽可能方便学生，使任意两点之间的最短路长度的总和最小。当然，从 $x$ 教学楼到 $y$ 教学楼的长度和从 $y$ 教学楼到 $x$ 教学楼的长度只需要统计一次。

输入格式

输入第 $1$ 行两个正整数 $n,m$（$n\le 100$，$m\le \dfrac{1}{2}n(n-1)$），代表教学楼和道路数量。

接下来 $m$ 行，每行三个正整数 $x_i,y_i,w_i$（$0<w_i\le 10^4$），表示在教学楼 $x_i$ 和 $y_i$ 之间有一条长度为 $w_i$ 的道路。

输入保证图连通，且不存在重边和自环。

输出格式

输出一行，表示在最优传送门设置方案下，所有无序点对之间最短路长度之和的最小值。

输入样例 #1

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

输出样例 #1

14

输入样例 #2

2 1
1 2 10000

输出样例 #2

0

输入样例 #3

3 3
1 2 1
1 3 10000
2 3 9999

输出样例 #3

2

数据范围

输入第 $1$ 行两个正整数 $n,m$（$n\le 100$，$m\le \dfrac{1}{2}n(n-1)$），代表教学楼和道路数量。

接下来 $m$ 行，每行三个正整数 $x_i,y_i,w_i$（$0<w_i\le 10^4$），表示在教学楼 $x_i$ 和 $y_i$ 之间有一条长度为 $w_i$ 的道路。

• $2\le n\le100$；

• $n-1\le m\le \dfrac{1}{2}n(n-1)$；

• $1\le x_i,y_i\le n$，$x_i\ne y_i$；

• $1\le w_i\le10^4$；