情

(friendship.cpp 1s/512M)

题目描述

这天小 Y 来到了“大厦王国”，她想和好朋友小 S 见面。大厦王国是一个奇妙的国度，这个国度由 $n$ 座独立的大厦组成，同时大厦和大厦间通过廊桥相连。廊桥是双向的，分低级和高级两种，小 Y 通过低级廊桥从一个大厦走到另一个大厦需要 $2$ 个单位时间，而通过高级廊桥则只需要 $1$ 个单位时间。由于小 Y 是游客，所以只有 $m$ 条廊桥可供她通行，不过好在她可以通过这些廊桥从一个大厦到达任意一个大厦。同时，在见到小 S 之前她不能在任何一座大厦内逗留，也就是说，当她走到某个大厦时，如果没有和小 S 会合，那么她必须立刻通过某条廊桥走向另一座大厦（即使这条廊桥可能是她刚刚走过的）。她把出发点选在了大厦 $1$，并和小 S 规划了 $q$ 个见面方案，第 $i$ 个方案可总结为 $(x_i,l_i,r_i)$，表示见面地点是大厦 $x_i$，约定见面时间处在小 Y 出发后的第 $[l_i,r_i]$ 个单位时间内（默认小 Y 出发时是时间节点 $0$）。小 Y 不想让小 S 久等，所以她希望知道，对于每个见面方案，$[l_i,r_i]$ 内有多少约定时间满足，存在一条从大厦 $1$ 到大厦 $x_i$ 的路线，使得小 S 在约定时间节点到达大厦 $x_i$ 时小 Y 也恰好到达大厦 $x_i$。你能帮帮她吗？

输入格式

第一行包含两个正整数 $n,m$，表示大厦数和小 Y 能通行的廊桥数。

接下来 $m$ 行，每行包含三个自然数 $x,y,o(o\in\{0,1\})$，表示大厦 $x,y$ 之间存在一条可供小 Y 通行的廊桥，如果 $o=0$ 则为高级廊桥，如果 $o=1$ 则为低级廊桥。

接下来一行包含一个正整数 $q$，表示见面方案数。

随后 $q$ 行，每行包含三个自然数 $x_i,l_i,r_i$，表示一个见面方案。

输出格式

共 $q$ 行，每行一个整数表示满足条件的约定时间的数量。

样例

样例输入 1

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

样例输出 1

2

样例输入 2

8 8
1 2 1
2 3 1
3 4 1
4 5 0
5 6 0
6 7 1
1 8 1
7 8 1
4
4 0 20
5 0 20
6 0 20
7 0 20

样例输出 2

8
7
8
8

数据范围

对于 $100\%$ 的数据，$1\le n,m,q\le 10^5,1\le x_i\le n,0\le l_i\le r_i\le 10^9$。