D. Shortest Path Query
time limit per test
2 seconds
memory limit per test
1024 МБ
input
standard input
output
standard output

You will be given a directed acyclic graph with $$$n$$$ vertices, labeled by $$$1,2,\ldots,n$$$. There are $$$m$$$ edges in the graph, each edge is either black or white. It is guaranteed that you can reach every vertex from the $$$1$$$-st vertex.

You will be given $$$q$$$ queries. In the $$$i$$$-th query, you will be given three integers $$$a_i$$$, $$$b_i$$$ and $$$x_i$$$. You need to report the length of the shortest path from the $$$1$$$-st vertex to the $$$x_i$$$-th vertex if we regard the length of each black edge as $$$a_i$$$ and regard the length of each white edge as $$$b_i$$$.

Input

The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n\leq 50\,000$$$, $$$1\leq m\leq 100\,000$$$), denoting the number of vertices and the number of directed edges.

In the next $$$m$$$ lines, the $$$i$$$-th line contains three integers $$$u_i$$$, $$$v_i$$$ and $$$c_i$$$ ($$$1\leq u_i \lt v_i\leq n$$$, $$$v_i-u_i\leq 1000$$$, $$$0\leq c_i\leq 1$$$), describing a directed edge from the $$$u_i$$$-th vertex to the $$$v_i$$$-th vertex. When $$$c_i=0$$$, its color is black, and when $$$c_i=1$$$, its color is white.

The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 50\,000$$$), denoting the number of queries.

Each of the next $$$q$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$x_i$$$ ($$$1\leq a_i,b_i\leq 10\,000$$$, $$$1\leq x_i\leq n$$$), denoting a query.

It is guaranteed that you can reach every vertex from the $$$1$$$-st vertex.

Output

For each query, print a single line containing an integer, denoting the length of the shortest path.

Example
Input
4 4
1 2 0
1 3 1
2 4 0
3 4 1
3
3 5 2
3 2 4
2 3 4
Output
3
4
4