正权无向图 G(n,m)G(n, m)G(n,m)，有 nnn 个点与 mmm 条边。你要回答 qqq 次询问，每次询问 u, vu,\ vu, v 两点，回答对于 u, vu,\ vu, v 两点，这张图上有多少条边在它们任意一条最短路上出现。
第一行三个正整数 n, m, qn,\ m,\ qn, m, q ，分别表示点的个数，边的个数，询问的个数。
接下来 mmm 行，每行三个正整数 u, , v, wu,\ ,\ v,\ wu, , v, w ，表示有一条连接 uuu 和 vvv 的无向边，边权为 www 。
接下来 qqq 行，每行两个正整数 u, vu,\ vu, v ，表示询问。
每个询问输出一行，一共输出 qqq 行。
对于每个询问，输出一个非负整数。表示对于询问的两点，这张图上有多少条边在它们间任意一条最短路上出现。
3 2 3 1 2 1 2 3 1 1 2 1 3 2 3
1 2 1
1≤n≤5001 \le n \le 5001≤n≤500
1≤m, q≤n⋅(n−1)/21 \le m,\ q \le n \cdot (n - 1) / 21≤m, q≤n⋅(n−1)/2
1≤u, v≤n1 \le u,\ v \le n1≤u, v≤n
1≤w≤10001 \le w \le 10001≤w≤1000
数据保证图上无重边和自环。