Sightseeing

Tourist sites are nodes and roads are bidirectional edges with quality values. A path quality is the minimum edge quality on the path. The hotel is node 1. For each destination, print the maximum achievable path quality from node 1.

The first line contains $,$, and $. Each of the next$ lines has endpoints $,$ and quality $(-- \le q \le 100000$). Each of the next $lines has a destination$ with
e 1$.

For each destination, print one line with the highest achievable path quality.

\le 500000$, \le 5000000$, \le V-1$