Shortest Path Tree Weight

Given an undirected weighted graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges, your task is to compute the total weight of the Shortest Path Tree (SPT) rooted at vertex 1. The SPT is constructed by running Dijkstra's algorithm starting from vertex 1, and the total weight is the sum of the weights of the edges chosen by the algorithm. Formally, if the SPT contains edges with weights \(w_1, w_2, \dots, w_k\), then the answer is \(\sum_{i=1}^{k} w_i\). If the graph is empty or no edges are selected, output 0.

inputFormat

The input is given via standard input. The first line contains two integers (n) and (m) (the number of vertices and edges). Each of the following (m) lines contains three integers (u), (v), and (w), describing an undirected edge between vertices (u) and (v) with weight (w).

outputFormat

Output a single integer representing the total weight of the Shortest Path Tree rooted at vertex 1. The output should be written to standard output.## sample

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

8