迪杰斯特拉

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/6/22
'''
有 N 个村庄，编号 1 到 N。

村庄之间有 M 条无向道路，第 i 条道路连接村庄 ai 和村庄 bi，长度是 ci。

所有村庄都是连通的。

共有 K 个村庄有商店，第 j 个有商店的村庄编号是 xj。

然后给出 Q 个询问，第 k 个询问给出一个村庄的编号 yk，问该村庄距离最近的商店有多远？

输入格式
第一行包含两个整数 N,M。

接下来 M 行，每行包含三个整数 ai,bi,ci，表示第 i 条道路连接村庄 ai 和村庄 bi，长度是 ci。

再一行包含整数 K。

接下来 K 行，每行包含一个整数 xj，表示第 j 个有商店的村庄编号是 xj。

再一行包含整数 Q。

接下来 Q 行，每行包含一个整数 yk，表示询问编号为 yk 的村庄与其距离最近的商店之间的距离。

输出格式
对于每个询问，输出该询问的结果。

数据范围
2≤N≤105,
N−1≤M≤min(N(N−1)2,105),
1≤Q≤105,
1≤K≤N,
1≤ci≤10000
输入样例：
7 7
1 2 5
1 4 3
2 3 2
2 5 1
3 6 7
5 6 8
6 7 6
3
7
5
4
7
1
2
3
4
5
6
7
输出样例：
3
1
3
0
0
6
0
'''
# 单源最短路径
# 迪杰斯特拉 + 超级源点
# 介绍：迪杰斯特拉是求单源最短距离，也就是求从某一源点出发到图中其他点的最短距离
from collections import deque, defaultdict
n, m = map(int, input().split())
g = {}  # 边的权重
nb = defaultdict(list)  # 邻接表
for i in range(m):
    a,b,c = map(int, input().split())
    # 由于是无向图，所以更新两个
    g[(a, b)] = c
    g[(b, a)] = c
    nb[a].append(b)
    nb[b].append(a)

k = int(input())
for i in range(k):
    # 输入商店编号
    x = int(input())
    # 初始化，将超级源点与商店的距离设置为0
    g[(0, x)] = 0
    # 因为不可以从x走回0（没有意义）所以g[(x, 0)]不写了
    # g[(x, 0)] = 0
    nb[0].append(x)

# 从0点出发，所以要把0点放进队列中
# 想给队列赋初始值必须加中括号！
de = deque([0])
# 迪杰斯特拉数组，因为我们多设置了一个超级源点，所以 n+1，初始的话超级源点到其他点的距离都为无穷
dist = [float('inf')] * (n+1)
dist[0] = 0
while de:
    t = de.popleft()
    for ni in nb[t]:    # 遍历t的所有邻居
        if dist[ni] > dist[t] + g[(t, ni)]:
            dist[ni] = dist[t] + g[(t, ni)]
            de.append(ni)

# dist构建完了
q = int(input())
for i in range(q):
    print(dist[int(input())])