You have an unweighted directed graph with ~N~ nodes and ~M~ edges. The ~i~th edge goes from node ~u_i~ to ~v_i~. You also have ~K~ other directed edges which are not currently in the graph. The ~i~th edge in this set has a color ~c_i~ and goes from node ~u_i~ to ~v_i~. You may add either ~1~ or ~2~ edges from this set onto the graph. If you add ~2~ edges, they must have different colors. Determine the minimum distance from node ~1~ to node ~N~ after adding the optimal edges, or output -1 if node ~N~ is still unreachable.

Constraints

~1 \leq N, M \leq 5\times10^3~

~1 \leq K \leq 10^6~

~1 \leq u_i, v_i \leq N~

~1 \leq c_i \leq 10^9~

Input Specification

The first line of input contains ~3~ space-separated integers ~N~, ~M~, and ~K~.

The next ~M~ lines each contain ~2~ space-separated integers, ~u_i~ and ~v_i~.

The next ~K~ lines each contain ~3~ space-separated integers, ~u_i~, ~v_i~, and ~c_i~.

Output Specification

Output a single integer, the minimum distance from node ~1~ to node ~N~ after adding the optimal ~2~ edges.

If it is impossible to reach node ~N~ from node ~1~, output -1.

Sample Input

7 7 5
1 2
2 3
1 4
4 5
3 5
6 5
7 6
1 5 1
3 7 3
3 4 3
1 3 2
5 7 1

Sample Output

2

Sample Input 2

9 4 7
1 2
2 3
3 4
4 9
1 8 1
8 9 1
1 7 1
7 9 1
1 6 1
6 5 2
5 9 3

Sample Output 2

4

Sample Input 3

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

Sample Output 3

3