Taco Delivery Time Problem

In this problem, you are given a city represented by n intersections and m directed roads connecting them. Each intersection may have a facility or not, as indicated by a binary list. Your task is to calculate the minimum travel time for delivery queries between pairs of intersections such that the delivery path passes through at least one intersection with a facility. Note that if the starting or ending intersection has a facility, it is considered as having visited a facility. If no such valid path exists, output -1.

Formally, let the city be represented as a graph with nodes \(1,2,\dots,n\). For each query with start \(s\) and target \(t\), find the shortest path from \(s\) to \(t\) that satisfies:

[ \exists, v \in path \text{ such that } f_v = 1, ]

where \(f_v\) is 1 if the intersection \(v\) has a facility, and 0 otherwise.

If no such path exists, return -1.

inputFormat

The input is given from standard input (stdin) as follows:

• The first line contains three integers: n (number of intersections), m (number of roads), and q (number of queries).
• The second line contains n integers, where each integer is either 0 or 1. The \(i\)-th integer indicates whether intersection \(i\) has a facility (1 means facility exists, 0 means not).
• Then follow m lines, each containing three integers x y d, representing a directed road from intersection x to intersection y with travel time d.
• After that, there are q lines, each with two integers s t, representing a query from start intersection s to target intersection t.

outputFormat

For each query, output one line containing a single integer - the minimum delivery time from the start to the target intersection that passes through at least one facility. If no such path exists, output -1.

## sample

6 7 2
1 0 1 0 0 1
1 2 4
1 3 2
2 3 5
2 4 10
3 5 3
4 6 8
5 6 1
1 6
4 6

6
8

</p>