템포럴 그래프

템포럴 그래프는 시간의 흐름에 따라 변화하는 관계를 표현하는 자료 구조이다. 템포럴 그래프를 구성하는 정점 집합 $V$는 시간의 흐름에 따라 변하지 않으며, 정점의 개수가 $n ≥ 1$이라 할 때 $V$는 $\\{0, 1, \dots , n - 1\\}$으로 나타낸다. 시간 표기 $T$는 양의 정수 $1, 2, \dots , t$의 값을 가지며 시간 표기가 차례로 증가하는 것으로 시간의 흐름을 표현한다. 각 시간 표기 $T$에서 양의 정수인 가중치를 가지는 간선들의 집합 $E\_T$가 정의되고, $E\_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 ≤ n ≤ 10\\,000$), 시간 표기의 범위를 나타내는 양의 정수 $t$ ($1 ≤ t ≤ 1\\,000$), 매 시간 표기마다 정의되는 간선들의 개수를 나타내는 양의 정수 $m$ ($1 ≤ m ≤ 1\\,000$)이 차례로 주어진다. 다음 줄에 경로의 시작이 되는 정점을 나타내는 정수 $s$와 경로의 끝이 되는 정점을 나타내는 정수 $e$ ($0 ≤ s ≠ e ≤ n - 1$)가 차례로 주어진다. 이어지는 $m$개의 줄은 시간 표기 $T = 1$에서 정의되는 간선들의 정보를 나타낸다. 특정한 두 정점을 연결하는 간선이 두 개 이상 나타나는 경우는 없다. 각 줄에는 간선이 연결하는 두 정점의 번호와 간선의 가중치를 나타내는 양의 정수 $w$ ($1 ≤ w ≤ 10\\,000$)가 차례로 주어진다. 이어지는 $m × (t − 1)$줄은 시간 표기 $T = 2, \dots , t$에서 정의되는 간선들의 정보를 동일한 방식으로 나타낸다.

출력은 표준출력을 사용한다. 정점 $s$에서 정점 $e$로 향하는 최단 길이 경로의 길이를 한 줄에 출력하고, 경로가 정의되지 않는 경우에는 $-1$을 출력한다.