题目描述

若干年后，宇宙中发现有 $N$ 个星球（编号从 $1$ 到 $N$）具有文明，并且其中的一些之间还建立了传送通道，使得各个星球上的居民可以相互往来。但是也有一些星球之间还处于敌对状态。

由于某些原因，你必须从你居住的 $1$ 号星球前往遥远的 $N$ 号星球。这是一次漫长的旅行，为了抵达目的地，你有可能会经过许多别的星球。由于有一些星球目前还处于敌对状态，因此你要避免同时经过这样的星球。比方说，如果星球 $A$ 和 $B$ 目前处于敌对状态，那么假如你访问过 $A$，之后就决不能再访问 $B$ 了（否则 $B$ 会认为你是间谍而将你囚禁起来），反之若你首先访问过 $B$，那么也不能再访问 $A$ 了。

现在你手上有一张星际地图，并且你已经知道哪些星球之间目前还处于敌对状态。那么，在不被囚禁的基础上，从起点到终点的最短路程究竟有多长呢？

输入格式

第一行为两个整数 $N$, $M$（$2 \leq N \leq 100$；$1 \leq M \leq 10000$）。

接下来 $M$ 行，每行三个整数 $A$, $B$, $D$（$1 \leq A, B \leq N$；$1 \leq D \leq 10000$），表示从星球 $A$ 到星球 $B$ 存在一条长度为 $D$ 的（单向）传送通道。

第 $M + 2$ 行为一个整数 $K$（$0 \leq K \leq 30$），表示有 $K$ 对星球目前处于敌对状态。

以下 $K$ 行，每行两个整数 $U$, $V$（$1 \leq U, V \leq N$ 且 $U \neq V$），表示星球 $U$ 和星球 $V$ 目前正处于敌对状态。

输入数据保证有解。

输出格式

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

样例输入

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

样例输出

4