Capital City Selection

In this problem, you are given a weighted undirected graph representing a network of cities connected by roads. Each road has an associated transportation cost. Let (d(u,v)) be the shortest path distance between cities (u) and (v). Your task is to choose a capital city such that the maximum distance from any city to the capital is minimized, i.e., choose city (x) that minimizes (\max_{1 \leq i \leq n} d(i,x)). In the case of ties, choose the city with the smallest index.

The input starts with two integers (n) and (m), representing the number of cities and roads respectively. The following (m) lines each contain three integers (u), (v), and (w), indicating that there is a bidirectional road between cities (u) and (v) with a transportation cost of (w).

inputFormat

The first line contains two integers (n) and (m) (where (n) is the number of cities and (m) is the number of roads). Each of the next (m) lines contains three integers (u), (v), and (w) representing a road between cities (u) and (v) with cost (w).

outputFormat

Output a single integer representing the index of the city selected as the capital, which minimizes the maximum distance from any city to the capital.## sample

2 1
1 2 1

1