Description
PIPI的世界有N个国家，PIPI现在想从1号国乘飞机飞往N号国，给出国家之间的往返航线以及单程机票费用。
现在PIPI获得了一张免费机票，用这张机票可以免费在指定的航线飞行一次。现在PIPI最少要花多少钱？
如果不存在从1号国到N号国的路线，输出“No way!”
Input
第一行两个整数,N,M，分别表示国家数以及航线数。（N<=10000,M<=200000）
接下来M行，每行三个整数u,v,c，分别表示航线连接的两个国家，以及单程机票费用。注意航线是可以往返的，也就是双向的。(c<=10000)
接下来一个整数k，表示免费机票可以使用的航线数。(k<=10000)
接下来k行，每行两个整数u,v，表示免费机票可乘坐的航线连接的两个国家。
Output
如果不存在从1号国到N号国的路线，输出“No way!”
否则一行输出一个整数，为使用免费机票的最小费用。
Sample Input
4 3
1 2 1
1 3 2
2 4 3
1
3 4