Given a connected weighted graph with $n$ vertices and $m$ edges, you are allowed to add an edge with weight 0 between any two vertices such that the total shortest path distances between all pairs of vertices is minimized. In other words, minimize:
$$ \sum_{i=1}^{n} \sum_{j=i+1}^{n} d(i,j) $$
where $d(i,j)$ is the shortest path distance between vertices $i$ and $j$.
### Input
- The first line contains two integers $n$ and $m$.
- The next $m$ lines each contain three integers $u$, $v$, and $w$, representing an edge between vertices $u$ and $v$ with weight $w$.
### Output
- Print a single integer, the answer to the problem.
### Constraints
- $1 \le n \le 100$
- $1 \le m \le \frac{n \times (n-1)}{2}$
- $1 \le u,v \le n$
- $1 \le w \le 10^4$
### Example
Input:
```
4 5
1 2 3
1 3 6
2 3 4
2 4 7
3 4 2
```
Output:
```
14
```
Explanation: Add an edge $(1,4)$ with weight $0$.
