시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 400 139 78 27.660%

문제

주언이는 경제학을 배워 행상인이 되었다. 두 도시를 오가며 장사를 하는데, 통행료의 합이 가장 적은 경로로 이동하려 한다. 도시들은 양방향 도로로 연결되어있으며, 도로마다 통행료가 존재한다.

그런데 정부는 세금 인상안을 발표하였다. 세금을 한 번에 올리면 문제가 발생할 수 있으므로 여러 단계에 걸쳐서 올린다고 한다. 세금이 A만큼 오르면 모든 도로의 통행료가 각각 A만큼 오르게 된다. 세금이 오르게 되면 주언이가 내야 하는 통행료가 변할 수 있다.

주언이를 도와 초기의 최소 통행료와 세금이 오를 때마다의 최소 통행료를 구하시오.

입력

첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다.

두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D)가 주어진다. 각각 출발 도시와 도착 도시 번호를 의미한다. 도시 번호는 1부터 시작한다.

다음 M개의 줄에는 각각 도로 정보를 나타내는 세 정수 a, b (1 ≤ a < b ≤ N), w (1 ≤ w ≤ 1,000)가 주어진다. 도시 a와 도시 b가 통행료 w인 도로로 연결되어 있다는 것을 의미한다.

다음 총 K개의 줄에는 각각 정수 p (1 ≤ p ≤ 10)가 주어진다. 각각 첫 번째, 두 번째, …, K 번째에 인상되는 세금을 의미한다.

S에서 D로 이동할 수 없는 경우는 주어지지 않는다.

출력

첫 번째 줄에 세금이 오르기 전의 최소 통행료를 출력한다.

두 번째 줄부터 K개의 줄에 각각 첫 번째, 두 번째, …, K 번째 세금이 올랐을 때의 최소 통행료를 출력한다.

예제 입력 1

3 3 2
1 3
1 3 5
1 2 1
2 3 2
1
2

예제 출력 1

3
5
8

힌트

세금이 오르기 전

첫 번째 세금 인상 후

두 번째 세금 인상 후