최단 경로 질의

정점이 $n$개인 방향 비순환 그래프가 주어진다. 정점에는 $1, 2, \ldots, n$번 번호가 붙어 있다. 그래프에는 $m$개의 간선이 있으며, 각 간선은 검은색 또는 흰색이다. 1번 정점에서 모든 정점에 도달할 수 있는 것이 보장된다.

질의가 $q$개 주어진다. $i$번째 질의에서는 정수 $a_i$, $b_i$, $x_i$가 주어진다. 검은색 간선의 길이를 $a_i$, 흰색 간선의 길이를 $b_i$로 볼 때, 1번 정점에서 $x_i$번 정점까지 가는 최단 경로의 길이를 구해야 한다.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다 ($1 \leq n \leq 50000$, $1 \leq m \leq 100000$).

다음 $m$개의 줄에는 $u_i$, $v_i$, $c_i$가 주어지며, 이는 $u_i$번 정점에서 $v_i$번 정점으로 가는 방향 간선을 뜻한다 ($1 \leq u_i < v_i \leq n$, $v_i - u_i \leq 1000$, $0 \leq c_i \leq 1$). $c_i = 0$이면 검은색, $c_i = 1$이면 흰색이다.

다음 줄에 질의 수 $q$가 주어진다 ($1 \leq q \leq 50000$). 이어지는 $q$개의 줄에는 $a_i$, $b_i$, $x_i$가 주어진다 ($1 \leq a_i, b_i \leq 10000$, $1 \leq x_i \leq n$).

각 질의마다 1번 정점에서 $x_i$번 정점까지 최단 경로의 길이를 한 줄에 출력한다.