Problem
최근 도청 뉴스에 비추어 두 강경 인터넷 거인 Uragania Laim.UR 그리고 "젠다" 서로의 데이터 센터 간에 안전한 통신 채널을 구축하는 것에 관한 계약에 서명하기로 결정했습니다. Uragania에는 n개의 도시가 있지만 불행히도 어떤 도시에도 두 거인의 데이터 센터가 없습니다. 따라서 안전한 채널을 형성하기 위해서는 장거리 통신 회선이 설치되어야 합니다.
회사의 전문가들은 통신 채널 세그먼트를 배치하여 연결할 수 있는 m 쌍의 도시를 식별하고 이러한 각 쌍에 대해 그러한 세그먼트를 생성하는 비용을 추정했습니다.
결과 채널은 여러 세그먼트로 구성될 수 있습니다. 첫 번째 회사의 데이터 센터가 있는 도시 중 하나에서 시작하여 중간 도시를 통과할 수 있으며 두 번째 회사의 데이터 센터가 있는 도시에서 끝나야 합니다.
이제 두 회사의 데이터 센터를 연결하는 보안 채널의 최소 비용을 결정해야 합니다.
입력:
첫 번째 줄에는 정수 n과 m이 포함됩니다(2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) — 링크 세그먼트로 연결할 수 있는 도시의 수와 도시 쌍의 수. 두 번째 줄에는 n 정수 ai(0 ≤ a
i ≤ 2)가 포함됩니다. a
i = 0이면 i번째 도시에 거인의 데이터 센터가 없습니다. ai = 1이면 "Laim.UR" 데이터 센터는 i번째 도시에 위치하고, a
i = 2이면 "Xenda" 데이터 센터는 i-번째 도시에 위치합니다. 번째 도시; . 이 숫자들 중 적어도 하나는 하나이고 하나는 둘이라는 것이 보장됩니다. 다음 m행 각각에는 3개의 정수 — s
i , t
i 및 c
i , 도시 s
i 및 t
i (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>)는 비용 ci(1 ≤ ci ≤ 105 )의 링크 세그먼트로 연결될 수 있습니다. 각 쌍의 도시는 최대 하나의 채널 세그먼트로 연결할 수 있습니다.
출력:
서로 다른 인터넷 거대 기업의 두 데이터 센터를 안전한 통신 채널로 연결할 수 있는 경우 출력 파일에 x, y 및 d의 세 가지 숫자를 인쇄합니다. 총 비용 d. 도시 x에는 데이터 센터 "Laim.UR"이 있어야 하고 도시 y에는 — 데이터 센터 "Xenda". 최적의 답변이 여러 개인 경우 하나를 인쇄하십시오. 필요한 채널을 그릴 수 없으면 -1을 출력합니다.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
6 7
1 0 1 2 2 0
1 3 3
1 2 4
2 3 3
2 4 2
1 6 5
3 5 6
5 6 1
| 3 4 5 |
| 2 |
4 2
1002
1 3 3
2 4 2
| -1 |
설명
첫 번째 예에서는 두 개의 세그먼트에서 통신 채널을 구축하는 것이 최적입니다. 3 − 2 및 2 .마이너스; 4.