Shortest Path Query

You are given a directed acyclic graph with $n$ vertices, labeled $1, 2, \ldots, n$. The graph has $m$ edges, and each edge is either black or white. Every vertex is reachable from vertex $1$.

You are given $q$ queries. In the $i$-th query, you get three integers $a_i$, $b_i$, and $x_i$. Give each black edge length $a_i$ and each white edge length $b_i$. Find the length of the shortest path from vertex $1$ to vertex $x_i$.

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 50000$, $1 \leq m \leq 100000$), the number of vertices and edges.

Each of the next $m$ lines contains $u_i$, $v_i$, and $c_i$, describing a directed edge from vertex $u_i$ to vertex $v_i$ ($1 \leq u_i < v_i \leq n$, $v_i - u_i \leq 1000$, $0 \leq c_i \leq 1$). The edge is black if $c_i = 0$ and white if $c_i = 1$.

The next line contains $q$ ($1 \leq q \leq 50000$), the number of queries. Each of the next $q$ lines contains $a_i$, $b_i$, and $x_i$ ($1 \leq a_i, b_i \leq 10000$, $1 \leq x_i \leq n$).

For each query, print one line containing the length of the shortest path from vertex $1$ to vertex $x_i$.