Emergency Service Station Location

You are given an undirected weighted graph representing intersections and the roads connecting them. Each road has a non-negative distance. Your task is to determine the optimal intersection at which to place an emergency service station.

The objective is to choose an intersection i such that the maximum distance from i to any other intersection, measured along the shortest path, is minimized. In mathematical terms, if d(i, j) denotes the shortest distance from intersection i to j, you must choose i such that:

\(\min_{i}\ \max_{j}\ d(i,j)\)

If there is more than one intersection with the same minimized maximum distance, choose the one with the smallest index. Note that the graph might be disconnected. In that case, the unreachable nodes are considered to have an infinite distance, and the intersection with the smallest index that minimizes the maximum distance among reachable intersections should be chosen.

inputFormat

The input starts with a line containing two integers \(n\) and \(m\): the number of intersections and the number of roads, respectively. Following this, there are \(m\) lines, each containing three integers \(u\), \(v\), and \(d\), which indicate that there is an undirected road between intersections \(u\) and \(v\) with a distance of \(d\).

outputFormat

Output a single integer: the index of the intersection that should be chosen for placing the emergency service station.

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

1