Gather All Servants

mzc, who is very wealthy, has n male servants. Now, mzc wants to gather all of them (for reasons unknown). The communication times between mzc and his servants via different channels are given. Consider a connected, weighted, undirected graph whose nodes are numbered from 0 to n, where node 0 represents mzc and each node i (1 ≤ i ≤ n) represents one servant. Each edge in the graph represents a bidirectional communication channel between two nodes with a transmission time t.

When mzc calls a servant, the message is relayed along the fastest available route. In order to gather all his servants, mzc must ensure that every servant receives the call. Hence, the total time required is the sum of the shortest communication times from node 0 to each servant.

Formally, if \(d(0,i)\) denotes the shortest communication time from node 0 to node \(i\), then the answer is:

\[ \text{Total Time} = \sum_{i=1}^{n} d(0,i)\]

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵), where n is the number of servants and m is the number of communication links.

Each of the next m lines contains three integers u, v, and t (0 ≤ u, v ≤ n, 1 ≤ t ≤ 10⁶), representing a bidirectional communication link between nodes u and v with a transmission time of t. It is guaranteed that the graph is connected.

outputFormat

Output a single integer: the total time required to call all servants, which is the sum of the shortest communication times from mzc (node 0) to each servant (nodes 1 through n).

sample

3 3
0 1 5
0 2 3
2 3 4

15