28169번 - Shortest Path Query 다국어

문제

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$.

입력

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<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.

출력

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

제한

힌트