Problem
Trước những tin tức về việc nghe lén gần đây, hai gã khổng lồ internet theo đường lối cứng rắn Uragania Laim.UR và "Xenda" đã quyết định ký thỏa thuận thiết lập kênh liên lạc an toàn giữa các trung tâm dữ liệu của nhau. Có n thành phố ở Uragania, nhưng thật không may, không có trung tâm dữ liệu nào của cả hai gã khổng lồ ở bất kỳ thành phố nào. Do đó, để hình thành một kênh an toàn, các đường dây liên lạc đường dài sẽ phải được đặt.
Các chuyên gia của các công ty đã xác định được m cặp thành phố có thể được kết nối bằng cách đặt phân khúc kênh truyền thông và ước tính chi phí tạo phân khúc như vậy cho mỗi cặp này.
Kênh kết quả có thể bao gồm một số phân đoạn. Nó phải bắt đầu ở một trong những thành phố nơi đặt trung tâm dữ liệu của công ty đầu tiên, nó có thể đi qua các thành phố trung gian và phải kết thúc ở thành phố nơi đặt trung tâm dữ liệu của công ty thứ hai.
Bây giờ cần phải xác định chi phí tối thiểu của một kênh an toàn kết nối trung tâm dữ liệu của hai công ty.
Đầu vào:
Dòng đầu tiên chứa số nguyên n và m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) — số lượng thành phố và số cặp thành phố có thể được kết nối bởi một đoạn liên kết. Dòng thứ hai chứa n số nguyên ai (0 ≤ a
i ≤ 2). Nếu a
i = 0, thì không có trung tâm dữ liệu của bất kỳ gã khổng lồ nào ở thành phố thứ i. Nếu ai = 1 thì trung tâm dữ liệu "Laim.UR" nằm ở thành phố thứ i và nếu a
i = 2 thì trung tâm dữ liệu "Xenda" nằm ở thành phố i- thành phố; . Đảm bảo rằng trong số này có ít nhất một số một và một số hai. Mỗi m dòng tiếp theo chứa ba số nguyên — s
i , t
i và c
i , có nghĩa là các thành phố s
i và t
i (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>) có thể được kết nối bằng một đoạn liên kết có giá ci (1 ≤ ci ≤ 105 ). Mỗi cặp thành phố có thể được kết nối với tối đa một phân đoạn kênh.
Đầu ra:
Nếu có thể kết nối hai trung tâm dữ liệu của những gã khổng lồ Internet khác nhau bằng một kênh liên lạc an toàn, thì in ra ba số trong tệp đầu ra: x, y và d, nghĩa là có thể thiết lập kênh liên lạc giữa các thành phố x và y với tổng chi phí d. Ở thành phố x nên có một trung tâm dữ liệu "Laim.UR", ở thành phố y — trung tâm dữ liệu «Xenda». Nếu có một số câu trả lời tối ưu, hãy in bất kỳ câu trả lời nào. Nếu không thể vẽ kênh cần thiết, hãy in −1.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 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
1 0 0 2
1 3 3
2 4 2
| -1 |
Giải thích
Trong ví dụ đầu tiên, cách tối ưu là xây dựng kênh liên lạc từ hai phân đoạn: 3 − 2 và 2 .trừ; 4.