Central Logistics Center

You are given a set of cities connected by bidirectional routes with positive distances. Your task is to determine the optimal city to build a central logistics center.

The optimal city is the one that minimizes the total travel distance from it to all other cities. In case multiple cities yield the same total distance, choose the city with the smallest index.

More formally, let \(d(u, v)\) be the shortest distance between cities \(u\) and \(v\). For each city \(i\) (\(1 \le i \le n\)), compute \(S(i)=\sum_{j=1}^{n}d(i,j)\). The goal is to find \(i\) such that \(S(i)\) is minimized. If there is a tie, the city with the lower index is chosen.

You may apply Dijkstra's algorithm to compute the shortest paths in the graph.

inputFormat

The input is read from standard input (stdin). The first line contains two integers (n) and (m), where (n) is the number of cities and (m) is the number of routes. Each of the next (m) lines contains three integers (u), (v), and (w), representing a bidirectional route between cities (u) and (v) with distance (w).

outputFormat

Print a single integer to standard output (stdout) representing the city number that should be chosen as the central logistics center.## sample

4 4
1 2 4
1 3 2
2 3 1
3 4 7

3