Problem1384--PIPI的飞行路线

1384: PIPI的飞行路线

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 292  Solved: 115
[Submit] [Status] [Web Board] [Creator:]

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

Sample Output

2

Source/Category