Walk#8258
Olympia, after reforming its transportation system, has become a prosperous country with beautiful cities and smooth roads. Each road has a unique beauty value, which determines the cost of traveling along it. The cost of a journey is defined by the highest beauty value among all the roads used. For example, if you travel on roads with beauty values [3, 1, 6, 4, 5], then the journey's cost is 6 coins. Each city has a specific type T_j, and types may repeat.
The country now plans to reform its tourism system by establishing tourist routes, each starting at city x_i and ending at city y_i. Each route must pass through at least k_i cities of different types.
Importantly, if you pay coins, you can travel any number of times on roads with a beauty value of or less, allowing for non-simple paths that may include cycles.
Given your success in previous reforms, the government seeks your expertise once more. For each specified route, determine the minimum possible cost. You can choose which cities to visit and which roads to take, as long as the path starts at city x_i, ends at y_i, and passes through at least k_i cities of different types.
The first line contains three integers , , and —the number of cities and roads in the country, and the number of routes to be evaluated.
The second line contains integers, where the -th integer specifies the type of the -th city T_j.
The following lines describe the roads. Each line contains three integers a_j, b_j, c_j, indicating a road between cities a_j and b_j with a beauty value of c_j.
The next lines describe the routes, each given by three integers x_i, y_i, k_i as outlined above.
Print integers, one per line. The integer on the -th line should be the minimum possible cost for the -th route. If a route is impossible, print -1.
مثال 1
مثال 2
In the first route of the first test case, you need to follow the path 3 \to 2 \to 1 \to 2 \to 3 \to 4. This involves traveling on roads with beauty values [3, 5, 5, 3, 2], so the cost of the path is 5.
25 points: 2 \leq N, M, Q \leq 100,\ k_i = 2
35 points: 2 \leq N, M, Q \leq 100
40 points: 2 \leq N, M \leq 10^5