Problem 1051. -- Space Trip

1051: Space Trip

Time Limit: 3 Sec  Memory Limit: 64 MB
Submit: 8  Solved: 3
[Submit][Status][Web Board]

Description

若干年后,宇宙中发现有 N 个星球(编号从 1 到 N)具有文明,并且其中的一些之间还建立了传送通道,使得各个星球上的居民可以相互往来。但是也有一些星球之间还处于敌对状态。
由于某些原因,你必须从你居住的 1 号星球前往遥远的 N 号星球。这是一次漫长的旅行,为了抵达目的地,你有可能会经过许多别的星球。由于有一些星球目前还处于敌对状态,因此你要避免同时经过这样的星球,比方说,如果星球 A 和 B 目前处于敌对状态,那么假如你访问过 A,之后就决不能再访问 B 了(否则 B 会认为你是间谍而将你囚禁起来),反之若你首先访问过 B,那么也不能再访问 A 了。
现在你手上有一张星际地图,并且你已经知道哪些星球之间目前还处于敌对状态。那么,在不被囚禁的基础上,从起点到终点的最短路程究竟有多长呢?

Input

第一行为两个整数 N,M(2 ≤ N ≤ 100;1 ≤ M ≤ 10000)。
接下来 M 行,每行三个整数 A,B,D(1 ≤ A,B ≤ N;1 ≤ D ≤ 10000)表示从星球 A 到星球 B 存在一条长度为 D 的(单向)传送通道。
第 M + 2 行为一个整数 K(0 ≤ K ≤ 30),表示有 K 对星球目前处于敌对状态。
以下 K 行,每行两个整数 U,V(1 ≤ U,V ≤ N 且 U ≠ V),表示星球 U 和星球 V 目前正处于敌对状态。
输入数据保证有解。

Output

输出一个整数,表示从 1 号星球到 N 号星球的最短路程。

Sample Input

4 5
1 2 1
1 3 4
2 3 1
2 4 3
3 4 1
1
2 3

Sample Output

4



HINT

Source

[Submit][Status]