Problem
Berdasarkan berita penyadapan baru-baru ini, dua gergasi internet garis keras Uragania Laim.UR dan "Xenda" memutuskan untuk menandatangani perjanjian untuk mewujudkan saluran komunikasi selamat antara pusat data masing-masing. Terdapat n bandar di Uragania, tetapi, malangnya, tiada pusat data kedua-dua gergasi di mana-mana bandar. Oleh itu, untuk membentuk saluran yang selamat, talian komunikasi jarak jauh perlu diletakkan.
Pakar syarikat telah mengenal pasti m pasangan bandar yang boleh disambungkan dengan meletakkan segmen saluran komunikasi dan menganggarkan kos mencipta segmen sedemikian untuk setiap pasangan ini.
Saluran yang terhasil mungkin terdiri daripada beberapa segmen. Ia mesti bermula di salah satu bandar di mana pusat data syarikat pertama terletak, ia boleh melalui bandar perantaraan dan mesti berakhir di bandar di mana pusat data syarikat kedua terletak.
Kini adalah perlu untuk menentukan kos minimum saluran selamat yang menghubungkan pusat data dua syarikat.
Input:
Baris pertama mengandungi integer n dan m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) — bilangan bandar dan bilangan pasangan bandar yang boleh dihubungkan dengan segmen pautan. Baris kedua mengandungi n integer ai (0 ≤ a
i ≤ 2). Jika a
i = 0, maka tiada pusat data mana-mana gergasi di bandar ke-i. Jika ai = 1, maka pusat data "Laim.UR" terletak di bandar ke-i, dan jika a
i = 2, maka pusat data "Xenda" terletak di i- bandar ke;. Dijamin bahawa di antara nombor ini terdapat sekurang-kurangnya satu satu dan satu dua. Setiap baris m seterusnya mengandungi tiga integer — s
i , t
i dan c
i , yang bermaksud bahawa bandar s
i dan t
i (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>) boleh disambungkan dengan segmen pautan kos ci (1 ≤ ci ≤ 105 ). Setiap pasangan bandar boleh dihubungkan oleh paling banyak satu segmen saluran.
Output:
Jika ada kemungkinan untuk menyambungkan dua pusat data gergasi Internet yang berbeza dengan saluran komunikasi yang selamat, kemudian cetak tiga nombor dalam fail output: x, y dan d, bermakna adalah mungkin untuk mewujudkan saluran komunikasi antara bandar x dan y dengan jumlah kos sebanyak d. Di bandar x perlu ada pusat data "Laim.UR", di bandar y — pusat data «Xenda». Jika terdapat beberapa jawapan yang optimum, cetak mana-mana satu. Jika mustahil untuk melukis saluran yang diperlukan, cetak &tolak;1.
Contoh
| # |
Input |
Output |
| 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 |
Penjelasan
Dalam contoh pertama, adalah optimum untuk membina saluran komunikasi daripada dua segmen: 3 &tolak; 2 dan 2 .tolak; 4.