国际旅行 Ⅱ
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

小龙突然穿越到异世界这里的国家划分并不同于之前的世界,具体的 目前有 n 个城市, m 条双向道路,确保所有城市联通,每个国家由若干个城市组成,若城市 u 和城市 v 之间存在至少两条路径所包含的边不具有交集,那么 u 和 v 属于同一个国家,否则属于不同的国家。
每条道路都需要花费一定的时间通过,若一条道路连接的两个城市属于不同国家,则该道路被称为国际道路.现在小龙提出 q 个问题,每个问题他想知道从城市 u 出发,只经过花费时间不超过 x 的国际道路(可以经过非国际道路,且没有限制),所到达的国家中城市个数第 k 小的国家所拥有的城市个数.。

输入描述:

第一行包含两个正整数 n,m 代表 n 个城市和 m 条双向道路.
(1 \leq n,m \leq 1e5)
接下来m行,每行包含三个正整数 u ,v, w 表示连接 u,v的道路需要花费w个单位时间通过。(1 \leq u,v \leq n)(1 \leq w \leq1e5)
接下来一行一个整数 q (1 \leq q \leq 1e5)
接下来q行每行三个整数 u ,x, k 代表从城市 u 出发 经过不超过 x 个单位时间的道路,所到达的国家中城市个数第 k 小的国家.
(1\leq u \leq n),(1\leq x,k \leq 1e5)
确保给出的图不具有重边和自环

输出描述:

输出 q 行,每行代表第 i 问题的答案,如果不存在拥有城市个数第 k 小的国家则输出-1。
示例1

输入

复制 
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

输出

复制 
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