Problem Y
Boiler Deliveries

You are an engineer working for Boiler Deliveries, a courier service that prides itself on making each route as enjoyable as possible, prioritizing driver satisfaction over speed. The area your company operates in contains $n$ cities (numbered $1, \ldots , n$) connected by $m$ one-way roads. These roads offers a range of driving experiences: some are smooth and scenic, while others are bumpy and stressful. Every road has a pleasure rating, which can be positive (a joy to drive) or negative (a real pain); the pleasure value of a path is the sum of the pleasure ratings of all roads traveled. To prevent excessive driving, the road network is designed so that no path starting and ending at the same city has a positive pleasure value.

Each delivery task includes a starting city $s$ where the vehicle is parked, a destination city $t$ where the item must be delivered, and a non-empty set of pickup cities $\{ v_1, \ldots , v_k \} $ where the desired item can be collected. A valid delivery path must

• Start at $s$ (to pick up the vehicle)

• Visit at least one of the pickup cities (to pick up the item)

• End at $t$ (to deliver the item).

It is guaranteed that $s \neq t$ and $s, t \not\in \{ v_1, \ldots , v_k \} $. Your manager has given you a list of upcoming delivery tasks. For each task, your job is to calculate the maximum pleasure value among all valid delivery paths for the drivers, or report that no valid path exists.

Input

The first line contains two integers, $3 \leq n \leq 800$ and $1 \leq m \leq 10^5$, where $n$ is the number of cities and $m$ is the number of roads. The cities are numbered from $1$ to $n$.

Each of the next $m$ lines contains three integers $1 \leq u, v \leq n$, and $-10^5 \leq p \leq 10^5$, indicating a one-way road from city $u$ to city $v$ with pleasure rating $p$. No road will start and end at the same city, and there will not be more than one road with the same starting and ending cities.

The next line contains an integer $1 \leq q \leq 2 \cdot 10^5$, the number of delivery tasks. Each of the following $q$ lines describes a task. Each line starts with two integers $s$ and $t$, indicating the start and destination cities, followed by an integer $k \geq 1$, the number of pickup cities for the task. Then follow $k$ distinct integers $v_1, \ldots , v_k$, representing the pickup cities. It is guaranteed that the sum of the $k$ values for all the tasks does not exceed $10^6$.

Output

For each delivery task, output a line containing a single integer, the maximum pleasure value for that task, or NO PATH if there are no valid delivery paths.

5 7
1 2 6
1 3 8
1 5 10
2 4 20
2 5 -1
4 3 8
5 4 -40
3
1 5 2 2 4
2 3 1 1
1 4 1 5

5
NO PATH
-30