세금

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

정부는 세금 인상안을 발표했다. 세금을 한 번에 올리면 문제가 생기므로 여러 단계에 걸쳐 올린다. 세금이 $A$만큼 오르면 모든 도로의 통행료가 각각 $A$만큼 오른다. 세금이 오르면 주언이가 내야 하는 통행료의 합도 달라진다.

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

첫째 줄에 세 정수 $N$ ($2 \le N \le 1000$), $M$ ($1 \le M \le 30000$), $K$ ($0 \le K \le 30000$)가 주어진다. 차례대로 도시의 수, 도로의 수, 세금 인상 횟수이다.

둘째 줄에 두 정수 $S$와 $D$ ($1 \le S, D \le N$, $S \ne D$)가 주어진다. 각각 출발 도시와 도착 도시의 번호이다. 도시 번호는 1부터 시작한다.

다음 $M$개 줄에는 도로 정보를 나타내는 세 정수 $a$, $b$ ($1 \le a < b \le N$), $w$ ($1 \le w \le 1000$)가 주어진다. 도시 $a$와 도시 $b$가 통행료 $w$인 도로로 이어져 있다는 뜻이다. 같은 두 도시를 잇는 도로가 여러 개 주어질 수도 있다.

그다음 $K$개 줄에는 정수 $p$ ($1 \le p \le 10$)가 한 줄에 하나씩 주어진다. 차례대로 첫 번째, 두 번째, …, $K$번째로 인상되는 세금이다.

$S$에서 $D$로 갈 수 없는 입력은 주어지지 않는다.

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

이어지는 $K$개 줄에 차례대로 첫 번째, 두 번째, …, $K$번째 세금 인상 직후의 최소 통행료를 출력한다.

세금이 오르기 전

첫 번째 세금 인상 후

두 번째 세금 인상 후