Minimum Travel Time to Visit All Libraries

You are given a network of libraries connected by bidirectional roads. There are n libraries and m roads. Each road connects two libraries and has an associated travel time. Starting from library 1, your task is to compute the minimum total travel time required to visit all libraries. If it is impossible to visit all libraries, output -1.

This problem can be solved using a Minimum Spanning Tree algorithm (such as Prim's algorithm). The MST of the network (if it exists) represents the optimal way to connect all libraries with minimal travel time.

Note: All formulas must be written in \( \LaTeX \) format. For example, the constraint on the number of libraries is given by \(1 \leq n \leq 10^5\) and the number of roads by \(0 \leq m \leq 2\times10^5\).

inputFormat

The first line contains two integers n and m representing the number of libraries and the number of roads respectively. Each of the following m lines contains three integers a, b, and t (\(1 \leq a, b \leq n\) and \(t\) is the travel time) denoting a road between libraries a and b with travel time t.

outputFormat

Output a single integer which is the minimum total travel time required to visit all libraries starting from library 1. If it is impossible to visit all libraries, output -1.

## sample

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

12

</p>