You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

  给定 $n$ 个点（$1 ∼ n$ 表示），$m$ 条边构成的图。

  第 $i$ 条边 $edges[i] = \{x, y, z\}$ 表示 $x$ 与 $y$ 之间有一条长度为 $z$ 的无向边。请你求出从 $1$ 号点到各点的最短路距离。

  数据范围：100%的数据满足：$1\leq n \leq 10^5, 1\leq m \leq 10^6, 1\leq z\leq 10^9$

Format

Input

  第一行为两个正整数$n,m$，分别表示点的数目和边的数目

  接下来$m$行，每行三个非负整数$u_i, v_i, w_i$，表示 $u_i$ 到 $v_i$ 有一条长度为 $w_i$ 的无向边。

  接下来一个整数 $r$，表示询问的次数

  最后一行为 $r \space (1 \leq r \leq 10^5)$ 个整数 $q_i \space (1 \leq q_i \leq n)$，表示询问从 $1$ 号点到 $q_i$ 号点的最短路距离，如果从 $1$ 号点不能到达 $q_i$ 号点，输出 $-1$

Output

  输出一行，共 $r$ 个整数，表示对于每个询问的回答

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