题目描述
小龙突然穿越到异世界这里的国家划分并不同于之前的世界,具体的 目前有 nnn 个城市, mmm 条双向道路,确保所有城市联通,每个国家由若干个城市组成,若城市 uuu 和城市 vvv 之间存在至少两条路径所包含的边不具有交集,那么 uuu 和 vvv 属于同一个国家,否则属于不同的国家。
每条道路都需要花费一定的时间通过,若一条道路连接的两个城市属于不同国家,则该道路被称为国际道路.现在小龙提出 qqq 个问题,每个问题他想知道从城市 uuu 出发,只经过花费时间不超过 xxx 的国际道路(可以经过非国际道路,且没有限制),所到达的国家中城市个数第 kkk 小的国家所拥有的城市个数.。
输入
第一行包含两个正整数 n,mn,mn,m 代表 nnn 个城市和 mmm 条双向道路.
(1≤n,m≤1e5)(1 \leq n,m \leq 1e5)(1≤n,m≤1e5)
接下来mmm行,每行包含三个正整数 u,v,wu ,v, wu,v,w 表示连接 u,vu,vu,v的道路需要花费www个单位时间通过。(1≤u,v≤n)(1≤w≤1e5)(1 \leq u,v \leq n)(1 \leq w \leq1e5)(1≤u,v≤n)(1≤w≤1e5)
接下来一行一个整数 q(1≤q≤1e5)q (1 \leq q \leq 1e5)q(1≤q≤1e5)
接下来qqq行每行三个整数 u,x,ku ,x, ku,x,k 代表从城市 uuu 出发 经过不超过 xxx 个单位时间的道路,所到达的国家中城市个数第 kkk 小的国家.
(1≤u≤n),(1≤x,k≤1e5)(1\leq u \leq n),(1\leq x,k \leq 1e5)(1≤u≤n),(1≤x,k≤1e5)
确保给出的图不具有重边和自环
输出
输出 qqq 行,每行代表第 iii 问题的答案,如果不存在拥有城市个数第 kkk 小的国家则输出-1。
样例输入 Copy
5 5
1 2 4
2 3 1
3 4 1
2 4 1
4 5 3
3
5 3 1
5 3 2
5 4 3
样例输出 Copy
1
3
3
提示
图中一共有三个国家 拥有的城市个数分别是 1 3 1
对于第一个询问:
从5出发只经过权值不超过3的国际道路所到达的国家所拥有的城市数量是:1,3
所以第1小的是1
对于第二个询问：
从5出发只经过权值不超过3的国际道路所到达的国家所拥有的城市数量是:1,3
所以第2小的是3
对于第三个询问：
从5出发只经过权值不超过4的国际道路所到达的国家所拥有的城市数量是:1,1,3
所以第3小的是3