Problem
Son telefon dinleme haberlerinin ışığında, iki katı internet devi Uragonia Laim.UR ve "Zenda" birbirlerinin veri merkezleri arasında güvenli iletişim kanalı kurulması konusunda anlaşma imzalama kararı aldı. Uragonia'da n şehir var ama ne yazık ki hiçbir şehirde her iki devin veri merkezi yok. Bu nedenle, güvenli bir kanal oluşturmak için uzun mesafeli iletişim hatlarının döşenmesi gerekecektir.
Şirketlerin uzmanları, bir iletişim kanalı segmenti oluşturarak birbirine bağlanabilecek m şehir çifti belirlediler ve bu çiftlerin her biri için böyle bir segment oluşturmanın maliyetini tahmin ettiler.
Ortaya çıkan kanal birkaç bölümden oluşabilir. Birinci firmanın veri merkezinin bulunduğu şehirlerden birinde başlamalı, ara şehirlerden geçebilmeli ve ikinci firmanın veri merkezinin bulunduğu şehirde bitmelidir.
Şimdi iki şirketin veri merkezlerini birbirine bağlayan güvenli bir kanalın minimum maliyetini belirlemek gerekiyor.
Giriş:
İlk satır n ve m tamsayılarını içerir (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) — bir bağlantı segmenti ile bağlanabilecek şehir sayısı ve şehir çifti sayısı. İkinci satır n tam sayı ai (0 ≤ a
i ≤ 2) içerir. a
i = 0 ise, o zaman i'inci şehirde devlerin hiçbirinin veri merkezi yoktur. ai = 1 ise "Laim.UR" veri merkezi i'inci şehirde, a
i = 2 ise "Xenda" veri merkezi i-'inci şehirde bulunuyor demektir. şehir; . Bu sayılar arasında en az bir bir ve bir iki olması garanti edilir. Sonraki m satırın her biri üç tam sayı içerir — s
i , t
i ve c
i , yani s
i ve t
i şehirleri (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>), maliyet ci'nin (1 ≤ ci ≤ 105 ) bir bağlantı segmenti ile bağlanabilir. Her bir şehir çifti en fazla bir kanal segmenti ile birbirine bağlanabilir.
Çıktı:
Farklı internet devlerinin iki veri merkezini güvenli bir iletişim kanalıyla birbirine bağlamak mümkünse, çıktı dosyasına üç sayı yazdırın: x, y ve d, yani x ve y şehirleri arasında bir iletişim kanalı kurmak mümkündür. toplam maliyet d. x şehrinde, y şehrinde bir "Laim.UR" veri merkezi bulunmalıdır — veri merkezi "Xenda". Birkaç uygun yanıt varsa, herhangi birini yazdırın. Gerekli kanalı çizmek mümkün değilse, &eksi;1 yazdırın.
Örnekler
| # |
Girdi |
Çıktı |
| 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 |
Açıklama
İlk örnekte, iki segmentten bir iletişim kanalı oluşturmak en uygunudur: 3 − 2 ve 2 .minus; 4.