Minimum Travel Cost

You are given a directed weighted graph with n nodes and m edges. The graph is described by a list of edges, where each edge is represented by three integers u, v, and w, indicating that there is an edge from node u to node v with a cost of w. Starting from node 1, your task is to calculate the minimum cost required such that you are able to reach every node in the graph.

If some node is unreachable from node 1, output -1. Otherwise, output the maximum among the shortest path costs from node 1 to each node.

The constraints are as follows:

• $1 \leq n \leq 100$
• $1 \leq m \leq 500$

Note: All formulas are provided in \(\LaTeX\) format.

inputFormat

The first line contains two integers n and m separated by a space.

The following m lines each contain three integers u, v, and w, representing an edge from node u to node v with cost w.

Formally, the input is provided as:

n m
u1 v1 w1
u2 v2 w2
... 
um vm wm

where \(1 \leq u_i, v_i \leq n\) and \(w_i\) is the cost of the edge from \(u_i\) to \(v_i\).

outputFormat

Output a single integer, which is the minimum travel cost to visit all nodes starting from node 1. If it is not possible to reach all the nodes, output -1.

## sample

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

6