#H63. 【拓展题】最短路径 Plus
【拓展题】最短路径 Plus
Description
给定 个点( 表示), 条边构成的图。
第 条边 表示 与 之间有一条长度为 的无向边。请你求出从 号点到各点的最短路距离。
数据范围:100%的数据满足:$1\leq n \leq 10^5, 1\leq m \leq 10^6, 1\leq z\leq 10^9$
Format
Input
第一行为两个正整数,分别表示点的数目和边的数目
接下来行,每行三个非负整数,表示 到 有一条长度为 的无向边。
接下来一个整数 ,表示询问的次数
最后一行为 个整数 ,表示询问从 号点到 号点的最短路距离,如果从 号点不能到达 号点,输出
Output
输出一行,共 个整数,表示对于每个询问的回答
Samples
4 6
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
3
1 2 3
0 2 4