Optimal Castle Location

You are given a kingdom with n towns numbered from 1 to n and m bidirectional roads connecting pairs of towns. Each road is associated with a travel time (cost). The king wants to build his castle in one of the towns such that the maximum travel time from that town to any other town is minimized.

More formally, for each town \( i \), let \( d(i) \) be defined as \[ d(i) = \max_{1 \le j \le n} \; \text{dist}(i,j), \] where \( \text{dist}(i,j) \) is the shortest distance between town \( i \) and town \( j \). Your task is to determine the town \( i \) such that \( d(i) \) is minimized. In the case of a tie, choose the town with the smallest identifier.

It is guaranteed that all towns are connected via some path and the roads are undirected. Solve the problem using, for example, the Floyd–Warshall algorithm.

inputFormat

The first line contains two integers n and m where n is the number of towns and m is the number of roads. The following m lines each contain three integers u, v, and w, representing a road between towns u and v with a travel time of w.

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

outputFormat

Output a single integer representing the identifier of the town where building the castle minimizes the maximum travel time to any other town. In case of a tie, output the smallest identifier.

Output Format:
 x

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

2