Minimum Delivery Time

You are given a weighted undirected graph representing the delivery network between N locations connected by M pathways. Each pathway is described by three integers u, v and t, representing a bidirectional route between locations u and v with a travel time of t.

Your task is to compute the minimum total travel time required to deliver packages to all locations. In other words, find the sum of the weights in a Minimum Spanning Tree (MST) of the graph. If it is impossible to reach all locations, output -1.

Note: If the graph contains only one node, the delivery time is 0.

The answer should be computed using algorithms such as Prim's or Kruskal's algorithm. All formulas are presented in \( \LaTeX \) as needed.

For example, if the graph is connected, the MST satisfies:

\[ \text{MST} = \min \left( \sum_{e \in E'} w_e \right) \quad \text{subject to connectivity of all nodes}, \] where \(E'\) is the set of edges chosen for the MST and \(w_e\) is the weight of edge \(e\).</p>

inputFormat

The input is given via standard input (stdin) and has the following format:

N M
u1 v1 t1
u2 v2 t2
... 
uM vM tM

Where:

• N is the number of locations (nodes).
• M is the number of pathways (edges).
• Each of the following M lines contains three integers u, v, and t representing a pathway between locations u and v with travel time t.

outputFormat

Output a single integer to standard output (stdout) which is the minimum total travel time required to deliver packages to all locations. If it is impossible because the graph is disconnected, output -1.

## sample

4 4
1 2 4
1 3 2
2 3 1
3 4 3

6

</p>