Description

In Chuanzhi Academy, there are $n$ teaching buildings and $m$ bidirectional roads connecting these buildings. There are no multiple edges or self-loops. Each road has a certain length, and every pair of buildings can be reached directly or indirectly through the roads. We can easily compute the shortest paths between these buildings.

To make transportation smoother, the school decides to add a pair of portals in two teaching buildings. The portals can directly reduce the distance between this pair of buildings to $0$. With the portals, the shortest path distances between some pairs of buildings become shorter.

Due to a limited budget, the school can only install one pair of portals. However, the principal wants to make it as convenient as possible for students, so the total sum of the shortest path lengths between any two points is minimized. Of course, the distance from building $x$ to building $y$ and the distance from building $y$ to building $x$ only need to be counted once.

Input Format

The first line contains two positive integers $n,m(n\le 100,m\le\frac{1}{2}n(n-1))$, representing the number of teaching buildings and roads.

The next $m$ lines each contain three positive integers $x_i,y_i,w_i(0 <w_i \le 10^4)$, indicating that there is a road of length $w_i$ between teaching buildings $x_i$ and $y_i$.

Output Format

Output one line: under the optimal plan, the sum of the shortest path lengths over all unordered pairs of points.

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

14

Hint

The sample is shown in the figure. When a pair of portals is built between buildings $1$ and $4$, the shortest path from $1$ to $2$ is $3$, from $1$ to $3$ is $0+2$, from $1$ to $4$ is $0$, from $2$ to $3$ is $4$, from $2$ to $4$ is $3+0$, and from $3$ to $4$ is $2$. The sum of shortest paths is $14$, which is the best plan.

Translated by ChatGPT 5