Longest Edge in the Minimum Spanning Tree

Bessie plans to investigate the hay situation of N farms (where \(2 \leq N \leq 2000\)) and starts from farm 1. There are M bidirectional roads (with \(1 \leq M \leq 10^4\)) connecting the farms. Note that there may be multiple roads between two farms and the total length of all roads does not exceed \(10^9\). The graph is guaranteed to be connected.

Bessie wishes to compute the length of the longest edge in the minimum spanning tree (MST) of this graph.

Note: Although Bessie starts from farm 1, the MST is constructed over the entire connected graph.

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of farms and roads respectively.

The next \(M\) lines each contain three integers \(u\), \(v\) and \(w\), representing a bidirectional road between farms \(u\) and \(v\) with length \(w\).

outputFormat

Output a single integer which is the maximum edge length in the minimum spanning tree of the graph.

sample

3 3
1 2 1
2 3 2
1 3 3

2