A city is served by a number of fire stations. Some
residents have complained that the distance from their houses
to the nearest station is too far, so a new station is to be
built. You are to choose the location of the fire station so as
to reduce the distance to the nearest station from the houses
of the disgruntled residents.
The city has up to $500$ intersections, connected by road
segments of various lengths. No more than $20$ road segments intersect at a
given intersection. The location of houses and firestations
alike are considered to be at intersections (the travel
distance from the intersection to the actual building can be
discounted). Furthermore, we assume that there is at least one
house associated with every intersection. There may be more
than one firestation per intersection.
The input begins with a single integer $1 \le t \le 100$ on a line by itself
indicating the number of testcases following, each of them as
described below. This line is followed by a blank line, and
there is also a blank line between two consecutive inputs.
The first line of each testcase contains two positive
integers: $f$,the number
of existing fire stations ($f \le
100$) and $i$, the
number of intersections ($i \le
500$). The intersections are numbered from $1$ to $i$ consecutively. $f$ lines follow; each contains the
intersection number at which an existing fire station is found.
A number of lines follow, each containing three positive
integers: the number of an intersection, the number of a
different intersection, and the length (between $1$ and $10\, 000$, inclusive) of the road
segment connecting the intersections. All road segments are
two-way (at least as far as fire engines are concerned), and
there will exist a route between any pair of intersections.
For each testcase, the output must follow the description
below. The outputs of two consecutive cases will be separated
by a blank line.
You are to output a single integer: the lowest intersection
number at which a new fire station should be built so as to
minimize the maximum distance from any intersection to the
nearest fire station.
|Sample Input 1
||Sample Output 1
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10