Forbidden Turns

문제

A GPS navigation company ICPC(International Control Perfection Company) designs a car navigation system for a transportation network. The system abstracts the transportation network as a directed graph $G(V,E)G(V,\; E)$ with edge cost $cc$. For a directed edge (v, w) ∈ E, $c(v,w)c(v,\; w)$ denotes the distance from a place v ∈ V to another place w ∈ V. The company wants to implement the shortest path module in the system. To reflect the normal situation that we cannot turn to some directions in a junction of transportation network, we want to find the shortest path that does not contain forbidden turns as a subpath.

A path from $vv$ to $ww$ is a sequence of vertices $(v_1,v_2,\cdots ,v_k)(v\_1,\; v\_2,\; \backslash cdots\; ,\; v\_k)$ where $v_1=vv\_1\; =\; v$, $v_k=wv\_k\; =\; w$, (v_i, v_{i+1}) ∈ E for 1 ≤ i ≤ k - 1. Unlike the common definition of the path, you are here allowed to repeat the same vertices in a path one or more. A subpath of a path is a contiguous subsequence of the sequence that corresponds to the path. A forbidden turn is a path (i.e., triplet) $(x,y,z)(x,\; y,\; z)$ such that x, y, z ∈ V and (x, y) ∈ E and (y, z) ∈ E. The distance of a path $(v_1,v_2,\cdots ,v_k)(v\_1,\; v\_2,\; \backslash cdots\; ,\; v\_k)$ is defined as ${\sum }_{i=1}^{k-1}c(v_i,v_{i+1})\backslash sum\_\{i=1\}^\{k-1\}\{c(v\_i,\; v\_\{i+1\})\}$. The shortest path from v ∈ V to w ∈ V is a path from $vv$ to $ww$ with the minimum distance. The company wants to find the distance of the shortest path that avoids the forbidden turns between two designated vertices. Note that the shortest path from v ∈ V to v ∈ V has distance $00$ and it avoids all the forbidden turns.

Let's see the following example in the figure below. Each edge cost lies beside each edge and the list of three forbidden turns are in the right box. The shortest path without forbidden turns from the vertex $33$ to the vertex $22$ is $(3,0,1,5,4,1,2)(3,\; 0,\; 1,\; 5,\; 4,\; 1,\; 2)$ which is denoted as blue arrows in the following figure. The distance of the shortest path is $3+12+4+7+8+2=363\; +\; 12\; +\; 4\; +\; 7\; +\; 8\; +\; 2\; =\; 36$. Note that we cannot take the shorter paths $(3,0,1,2)(3,\; 0,\; 1,\; 2)$ and $(3,0,1,5,2)(3,\; 0,\; 1,\; 5,\; 2)$ since they contain forbidden turns $(0,1,2)(0,\; 1,\; 2)$ and $(1,5,2)(1,\; 5,\; 2)$, respectively.

Given a directed graph $G(V,E)G(V,\; E)$ with the edge cost $cc$, a set of forbidden turns $FF$, and two vertices $vv$ and $ww$, write a program to output the distance of the shortest path from $vv$ to $ww$ that avoids all the forbidden turns. We assume that out-degree of each vertex $vv$, i.e., the number of edges that starts from $vv$ is at most $1010$.

입력

Your program is to read from standard input. The input starts with a line containing three integers, $mm$, $nn$, and $kk$. (0 ≤ m ≤ 10n, 1 ≤ n ≤ 30\,000, 0 ≤ k ≤ 500\,000), where $mm$ is the number of directed edges, $nn$ is the number of vertices, and $kk$ is the number of forbidden turns of the given directed graph $G(V,E)G(V,\; E)$. Here, $kk$ is less than or equal to the number of all the possible forbidden turns in the given directed graph $G(V,E)G(V,\; E)$. The vertices are numbered from $00$ to $n-1n\; -\; 1$. The second line contains two integers $vv$ and $ww$ which denote the source and destination vertices, respectively. In the following mm lines, the $ii$-th line contains three integers $x_{i}x\_i$, $y_{i}y\_i$, and $c_{i}c\_i$ (0 ≤ x_i ≠ y_i ≤ n - 1 and 0 ≤ c_i ≤ 10^3) which denotes an edge (x_i, y_i) ∈ E and its cost, respectively. In the following $kk$ lines, the $ii$-th line contains three integers $x_{i}x\_i$, $y_{i}y\_i$, and $z_{i}z\_i$ which denote a forbidden turn $(x_i,y_i,z_i)(x\_i,\; y\_i,\; z\_i)$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain an integer that represents the distance of the shortest path from $vv$ to $ww$ which avoids all the forbidden turns. If such a path does not exist, the line should contain $-1-1$.

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

36

4 4 1
0 3
0 1 2
1 2 3
0 2 7
2 3 10
0 1 2

17

4 4 0
0 3
0 1 2
1 2 3
0 2 7
2 3 10

15