Security System Installation

There is a network of N computers. Some pairs of computers are directly connected by communication lines, and two computers can communicate either through a direct line or through other computers.

Computers and lines can have different performance, so each direct line may require a different amount of communication time. In some cases, a route through other computers can be faster than using a direct line. If communication uses multiple lines, the required time is the sum of the times of those lines.

One day, a hacker broke into the network. The administrator blocked all lines and computers to stop the attack, then decided to install a security system on exactly one computer. When a computer is attacked, the incident is delivered through the network, and the computer with the security system sends a security packet. After preparation, the network will be restored under the following conditions.

1. Because another attack is possible, restore as few lines as possible. However, after restoration, every pair of different computers must still be able to communicate.
2. Since the attacked computer is unknown in advance, choose the installation computer so that the average communication time from it to all other computers is minimized.

Given the original network, find the number of the computer where the security system should be installed.

The first line contains two integers N (1 <= N <= 200) and M (1 <= M <= 10,000).

Each of the next M lines contains three integers A, B, and C, describing one line. It means computer A and computer B are connected by a line whose communication time is C. Computers are numbered from 1 to N. C is a positive integer not greater than 10,000.

All communication is fully bidirectional, so two computers connected by one line can communicate in either direction.

Print the number of the computer where the security system should be installed.

If there is more than one answer, print the smallest number among them.