Optimal Teleporter Installation

You are given an undirected connected graph with n nodes (buildings) and m edges (roads). There are no self-loops or multiple edges. Each road has a positive integer length. It is guaranteed that every building is reachable from any other building using the existing roads.

The school administration can install exactly one pair of teleporter portals between two distinct buildings. This teleporter acts as a bidirectional edge with weight 0. After adding the teleporter between nodes x and y, the new shortest distance between any two nodes i and j becomes:

$$d'(i,j)=\min\{d(i,j),\;d(i,x)+d(y,j),\;d(i,y)+d(x,j)\}, $$

where d(i, j) is the original shortest distance between nodes i and j.

Your task is to choose a pair of nodes to install the teleporter such that the sum of the shortest distances over all unordered pairs of distinct nodes,

$$S=\sum_{1 \le i < j \le n}d'(i,j),$$

is minimized. Output the minimum possible total sum.

inputFormat

The input begins with a line containing two integers n and m (n is the number of nodes and m is the number of edges).

Then follow m lines, each containing three integers u, v, and w indicating that there is an undirected edge between nodes u and v with weight w. Nodes are numbered from 1 to n.

outputFormat

Output a single integer representing the minimum total sum of shortest distances between every unordered pair of buildings after the optimal teleporter installation.

sample

3 3
1 2 1
2 3 1
1 3 3

2