E. Maze of Time
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A certain laboratory consists of $$$n$$$ rooms connected by $$$m$$$ bidirectional corridors, which require a certain amount of time to traverse. Mysterious experiments with time were conducted in the laboratory, resulting in the discovery that if one follows a certain route and visits some pairs of corridors, the time spent will increase by a certain amount, even though it should not happen at first glance. The chief scientist learned about this and plans to go to the main room of the laboratory $$$n$$$ to fix the anomalies. Initially, he is in room $$$1$$$.

Help him determine the minimum time he needs to reach room $$$n$$$. If it is impossible to get from room $$$1$$$ to room $$$n$$$, output $$$-1$$$.

Input

The first line contains 3 integers $$$n, m$$$, and $$$k\, (1 \le n \le 10^5,\, 1 \le m \le 10^5,\, 0 \le k \le 5)$$$ — the number of rooms in the laboratory, the number of corridors, and the number of pairs of special corridors.

The next $$$m$$$ lines each contain 3 integers $$$u, v$$$, and $$$t$$$, indicating that there is a bidirectional passage between rooms $$$u$$$ and $$$v$$$, which takes $$$t$$$ time to traverse $$$(1 \le u,v \le n,\, 1 \le t \le 10^9)$$$.

Then, in $$$k$$$ lines, there are 3 integers $$$i,\, j$$$, and $$$t\, (1 \le i,j \le m,\, i \ne j,\, 1 \le t \le 10^9)$$$, indicating that if the scientist visits both corridor number $$$i$$$ and corridor number $$$j$$$ (in any order) on the way from $$$1$$$ to $$$n$$$, the time of his journey will increase by $$$t$$$.

It is guaranteed that all $$$2 \cdot k$$$ corridor numbers that increase time are distinct.

Output

In a single line, output the answer to the problem.

Examples
Input
5 6 2
1 2 2
2 3 6
3 5 3
2 5 7
1 4 5
4 5 1
5 6 10
1 3 10
Output
9
Input
5 6 3
1 2 2
2 3 6
3 5 3
2 5 7
1 4 5
4 5 1
5 6 14
1 4 100
2 3 10
Output
20