Walk
Olympia, after reforming its transportation system, has become a prosperous nation with stunning 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 of the roads used. For instance, if you travel on roads with beauty values [3, 1, 6, 4, 5], the journey's cost would be 6 coins. Each city j has a specific type T[j], and these types may repeat.
The country now plans to reform its tourism system by establishing q 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 f coins, you can travel any number of times on roads with a beauty value of f 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.
Input
The first line contains three integers N, M, and Q - representing the number of cities and roads in the country, and the number of routes to be evaluated.
The second line contains N integers, where the j-th integer specifies the type of the j-th city T[j].
The following M 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 q lines describe the routes, each given by three integers x[i], y[i], k[i] as outlined in the conditions.
1 ≤ T[j] ≤ 10^51 ≤ c[j] ≤ 10^51 ≤ a[j], b[j], x[i], y[i] ≤ N2 ≤ k[i] ≤ N1 ≤ q ≤ 10^4
Output
Output q integers, one per line. The integer on the i-th line should be the minimum possible cost for the i-th route. If a route is impossible, output -1.
Scoring
25 points for 2 ≤ N, M, Q ≤ 100,
k[i]= 235 points for 2 ≤ N, M, Q ≤ 100
40 points for 2 ≤ N, M ≤
10^5
Examples
Note
In the first route of the first test case, you need to follow the path 3 → 2 → 1 → 2 → 3 → 4. This involves traveling on roads with beauty values [3, 5, 5, 3, 2], resulting in a path cost of 5.