Fire Station#1059
A city is served by several fire stations. Some residents have complained that the distance from their houses to the nearest fire station is too great, and have requested that a new fire station be built. The location for the new station should be chosen so that the maximum distance from any intersection to the nearest fire station is minimized.
The city has at most intersections connected by roads of various lengths. No more than roads can meet at any intersection. Both houses and fire stations are located at intersections (the distance from the intersection to the actual building is considered zero). There is at least one house at each intersection. There may be more than one fire station at an intersection.
The first line contains two positive integers: (f \leq 100) — the number of existing fire stations, and (i \leq 500) — the number of intersections. Intersections are consecutively numbered from to . The next lines each contain the number of the intersection where a fire station is located. Each of the following lines contains three positive integers: the numbers of two intersections connected by a road, and the length of that road. All roads are two-way, and any two intersections are connected by some route.
Output one integer: the smallest intersection number at which a new fire station should be built to minimize the maximum distance from any intersection to the nearest fire station.
Example 1