금지된 회전

ICPC(International Control Perfection Company)는 교통망을 위한 자동차 내비게이션 시스템을 설계한다. 이 시스템은 교통망을 간선 비용 $c$가 붙은 방향 그래프 $G(V, E)$로 나타낸다. 방향 간선 $(v, w) \in E$에 대해 $c(v, w)$는 장소 $v$에서 장소 $w$까지의 거리이다. 회사는 이 시스템에 들어갈 최단 경로 모듈을 구현하려고 한다. 교차로에서는 일부 방향으로 회전할 수 없으므로, 금지된 회전을 부분 경로로 포함하지 않는 최단 경로를 찾아야 한다.

$v$에서 $w$까지의 경로는 $v_1 = v$, $v_k = w$이고 $1 \le i \le k-1$에 대해 $(v_i, v_{i+1}) \in E$인 수열 $(v_1, v_2, \cdots, v_k)$이다. 일반적인 정의와 달리 경로에서 같은 정점을 반복해도 된다. 부분 경로는 경로의 연속된 부분 수열이다. 금지된 회전은 $(x, y) \in E$이고 $(y, z) \in E$인 세 쌍 $(x, y, z)$이다. 경로 $(v_1, \cdots, v_k)$의 거리는 $\sum_{i=1}^{k-1} c(v_i, v_{i+1})$이다. $v$에서 $w$까지의 최단 경로는 거리가 가장 작은 경로이다. $v$에서 $v$까지의 최단 경로 거리는 0이며, 이 경로는 금지된 회전을 하나도 포함하지 않는다.

방향 그래프, 금지된 회전의 집합 $F$, 두 정점 $v$와 $w$가 주어졌을 때, 모든 금지된 회전을 피하는 $v$에서 $w$까지 최단 경로의 거리를 구하라. 각 정점의 출차수는 최대 10이다.

첫 줄에 정수 $m$, $n$, $k$가 주어진다 ($0 \le m \le 10n$, $1 \le n \le 30000$, $0 \le k \le 500000$). $m$은 방향 간선의 수, $n$은 정점의 수, $k$는 금지된 회전의 수이다. 정점은 0부터 $n-1$까지 번호가 매겨져 있다. 둘째 줄에는 출발 정점 $v$와 도착 정점 $w$가 주어진다. 이어지는 $m$개 줄에는 $x_i$, $y_i$, $c_i$가 주어지며, 간선 $(x_i, y_i)$와 그 비용 $c_i$를 뜻한다 ($0 \le x_i$, $x_i \ne y_i \le n-1$, $0 \le c_i \le 10^3$). 마지막 $k$개 줄에는 금지된 회전 $(x_i, y_i, z_i)$가 주어진다.

금지된 회전을 모두 피하는 $v$에서 $w$까지 최단 경로의 거리를 한 줄에 출력한다. 그런 경로가 없으면 -1을 출력한다.