Longest Shortest Path from the Capital

You are given a network of towns connected by bidirectional roads. The capital is town 1. Your task is to determine the longest distance among the shortest paths from the capital to every other town.

Formally, given \(N\) towns and \(M\) roads, each road is described by three integers \(u\), \(v\), and \(l\) where \(l\) is the length of the road connecting towns \(u\) and \(v\). Compute the shortest path from town 1 (the capital) to every other town, and then output the maximum of these distances.

If there is only one town, output 0.

inputFormat

The first line of input contains two integers \(N\) and \(M\) — the number of towns and the number of roads respectively.

The next \(M\) lines each contain three integers \(u\), \(v\), and \(l\), denoting that there is a bidirectional road connecting towns \(u\) and \(v\) with length \(l\).

You may assume that the towns are numbered from 1 to \(N\), with the capital being town 1.

outputFormat

Output a single integer — the longest distance among the shortest paths from the capital (town 1) to all the other towns.

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

11