시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 148 78 73 52.143%

문제

만약 KIST 기사단 2기로 여러분이 선발된다면, 서울 월곡에 있는 KIST와 양재에 있는 씨알푸드에서 팀이 함께 만나 의논하고 함께 작업할 시간을 가지게 된다. 누구나 그 회의 장소에 빨리 가고 싶은 마음은 똑같을 것이다.

각 장소를 노드로 생각하고, 연결된 도로를 간선으로 생각하면 그래프를 구성할 수 있다. KIST 기사단 N명의 집이 있는 노드 번호와 KIST, 씨알푸드의 노드 번호가 주어지고, 한 사람의 거리 di = (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)로 정의된다. 단, 도달할 수 없는 경우의 최단 거리는 -1로 정의한다. 예를 들어, 어떤 사람이 KIST로는 갈 수 없고 씨알푸드까지의 최단 거리가 10인 경우 이 사람의 거리 d는 9이고, 다른 사람이 KIST, 씨알푸드로 모두 갈 수 없을 경우 이 사람의 거리 d는 -2이다. 이 때 Σdi의 값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000)

둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V)

셋째 줄에 팀원 N명의 집의 위치 Hi가 공백을 사이에 두고 주어진다. (1 ≤ i ≤ N, 1 ≤ Hi ≤ V)

넷째 줄부터 E+3번째 줄까지는 도로의 양 끝 장소 a, b와 길이 l이 주어진다. (1 ≤ a, b ≤ V, 1 ≤ l ≤ 100)

출력

모든 사람의 최단 거리의 합을 출력한다. 단, KIST나 씨알푸드로 갈 수 없는 경우에는 -1로 처리한다.

예제 입력

2 5 10
3 5
2 4
3 2 91
1 3 44
5 3 93
1 4 1
4 5 53
4 2 23
5 1 60
2 1 63
3 4 38
5 2 17

예제 출력

156

힌트