템포럴 그래프

템포럴 그래프는 시간에 따라 변하는 관계를 표현하는 자료 구조이다. 템포럴 그래프의 정점 집합 $V$는 시간이 흘러도 변하지 않는다. 정점의 개수를 $n \ge 1$이라 하면 $V = \{0, 1, \dots, n-1\}$이다. 시간 표기 $T$는 양의 정수 $1, 2, \dots, t$의 값을 가지며, 시간 표기가 커질수록 시간이 흐른다. 각 시간 표기 $T$에서 양의 정수 가중치를 가지는 간선들의 집합 $E_T$가 정의되고, $E_T$에 포함되는 간선의 수는 모든 $T$에서 같다. 아래 그림은 정점 집합 $V = \{0, 1, 2, 3, 4\}$와 시간 표기 $T = 1, 2, 3, 4$에서 정의된 템포럴 그래프의 예시이다.

템포럴 그래프에서 한 정점에서 다른 정점으로 가는 경로는 시간 표기가 증가하는 순서로 나타나는 간선들의 집합이다. 경로를 만들 때 각 시간 표기에서 간선을 최대 한 개 선택할 수 있으며, 경로를 이루는 간선들의 시간 표기가 연속일 필요는 없다. 위 그림의 그래프에서 간선 $(0, 1)$, $(1, 2)$, $(2, 4)$를 각각 시간 표기 $T = 1, 2, 4$에서 선택하면 정점 $0$에서 정점 $4$로 가는 경로가 된다. 반면 간선 $(0, 2)$, $(2, 3)$, $(3, 4)$를 각각 시간 표기 $T = 1, 3, 2$에서 선택하면 선택한 시간 표기가 증가하지 않으므로 정점 $0$에서 정점 $4$로 가는 경로가 될 수 없다. 경로의 길이는 경로에 포함된 간선 가중치의 합으로 정의한다. 간선 $(0, 2)$, $(2, 4)$를 각각 시간 표기 $T = 1, 4$에서 선택하면 정점 $0$에서 정점 $4$로 가는 최단 경로이며, 길이는 $1 + 2 = 3$이다.

입력으로 템포럴 그래프와 경로의 시작 정점 $s$, 끝 정점 $e$가 주어질 때, 정점 $s$에서 정점 $e$로 가는 최단 경로의 길이를 구하는 프로그램을 작성하시오.

첫 번째 줄에 정점 집합의 크기 $n$ ($2 \le n \le 10\,000$), 시간 표기의 범위 $t$ ($1 \le t \le 1\,000$), 매 시간 표기마다 정의되는 간선의 개수 $m$ ($1 \le m \le 1\,000$)이 차례로 주어진다. 다음 줄에는 경로의 시작 정점 $s$와 끝 정점 $e$ ($0 \le s \ne e \le n - 1$)가 차례로 주어진다. 이어지는 $m$개의 줄에는 시간 표기 $T = 1$에서 정의되는 간선의 정보가 주어진다. 각 줄에는 간선이 연결하는 두 정점의 번호와 간선의 가중치 $w$ ($1 \le w \le 10\,000$)가 차례로 주어진다. 두 정점을 연결하는 간선이 두 개 이상 주어지는 경우는 없다. 이어지는 $m \times (t - 1)$개의 줄에는 시간 표기 $T = 2, \dots, t$에서 정의되는 간선의 정보가 같은 방식으로 주어진다.

정점 $s$에서 정점 $e$로 가는 최단 경로의 길이를 한 줄에 출력한다. 경로가 존재하지 않으면 $-1$을 출력한다.