2761: 完美路径

“Lostland”主题公园新开了一个迷宫城，整个迷宫由n个房间和m条通道组成。每个通道被漆成了颜色ci。每个参赛者被直升机空投到了房间1，他们的任务是走到房间n。 公园拥有者准备举行一场竞赛，参赛选手们被空投至房间1，当他们到达房间n时，将经过通道的颜色序列写下，序列最短的人获胜。如果有多个选手的序列最短，那么字典序小的人胜。 Gaosh是一名参赛者，他在直升机上拍下了迷宫的全景，现在他需要你帮他找出一条“完美路径”，首先要满足序列最短，其次是字典序要尽可能小。

   第1行：两个数n和m（2<=n<=100000,1<=m<=200000）。    第2~m+1行：每行三个数ai，bi，ci，表示房间ai和bi之间有一条颜色为ci的双向边，1<=ci<=10^9。  

   第1行：一个数k表示最短的序列长度。    第2行：一行k个数，给出颜色序列，空格隔开。

4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

2
1 3