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.