B.留春春不住，春归人寂寞。
题号：NC232145
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

又是一年一度的新生校赛，但是acm集训队的sunshine关注的重点却不仅仅是校赛，因为校赛结束了意味着sunshine不久之后就可以在春节的时候回家去找好朋友（以下称呼为小w）一起玩，这样就不会寂寞了，好耶！

sunshine和小w的家乡是美丽的河南长垣。这里有纷繁复杂的公交线路，但是总共有n个站点（站点编号为1~n）。sunshine每次都坐公交去找小w，在寒假的某一天，sunshine和小w约定在小w所在的站点集合，sunshine在编号为1的站点，小w在编号为x的站点，由于公交车从一个站点u到相邻的站点v，需要花费时间t。但是小w每次所在位置都不一定（x不是固定的站点编号），因此sunshine想询问q次，每次sunshine想预先知道坐公交车去和小w集合在路上花费的最短时间（保证从1开始可以到任何站点）。

输入描述:

第1行给出n和m分别表示公交站点数和站点相邻的数量。

接下来的m行给出u,v,t。

表示公交车从站点u到站点v所需要的时间为t。

第行一个数字q，代表q次询问。

接下来q行，每行给出一个x，代表小w所在的公交站点。

输出描述:

对于每次询问输出从站点1到站点x所需要的最短时间。

数据范围：



示例1

输入

复制 
3 3
1 2 1
2 3 1
1 3 3
3
1
2
3

输出

复制 
0
1
2

说明

从编号为1的站点出发，位置没有变，最短时间为0。
从编号为1的站点出发，到编号为2的站点，如果走1 – 2，时间花费为1，但是1 – 3 – 2 时间花费为4，因此最短时间为1。
从编号为1的站点出发，到编号为3的站点，如果走1 – 3，时间花费为3，但是1 – 2 – 3 时间花费为2，因此最短时间为2。