给定一个有向无环图，顶点编号为 $1, 2, \dots, n$。图中共有 $m$ 条边，每条边要么是黑色，要么是白色。保证从 1 号顶点可以到达图中每一个顶点。

你需要处理 $q$ 次查询。在第 $i$ 次查询中，给定三个整数 $a_i, b_i$ 和 $x_i$。你需要计算从 1 号顶点到 $x_i$ 号顶点的最短路径长度，其中黑色边的长度视为 $a_i$，白色边的长度视为 $b_i$。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 50\,000, 1 \le m \le 100\,000$)，分别表示顶点数和有向边数。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i, v_i$ 和 $c_i$ ($1 \le u_i < v_i \le n, v_i - u_i \le 1\,000, 0 \le c_i \le 1$)，描述一条从 $u_i$ 号顶点到 $v_i$ 号顶点的有向边。当 $c_i = 0$ 时，该边为黑色；当 $c_i = 1$ 时，该边为白色。

下一行包含一个整数 $q$ ($1 \le q \le 50\,000$)，表示查询次数。

接下来的 $q$ 行中，每行包含三个整数 $a_i, b_i$ 和 $x_i$ ($1 \le a_i, b_i \le 10\,000, 1 \le x_i \le n$)，表示一次查询。

保证从 1 号顶点可以到达图中每一个顶点。

输出格式

对于每次查询，输出一行，包含一个整数，表示最短路径的长度。

样例

样例输入 1

4 4
1 2 0
1 3 1
2 4 0
3 4 1
3
3 5 2
3 2 4
2 3 4

样例输出 1

3
4
4