Problem
Alla luce delle recenti notizie sulle intercettazioni, i due giganti di internet intransigenti Uragania Laim.UR e "Xenda" ha deciso di firmare un accordo sulla creazione di un canale di comunicazione sicuro tra i rispettivi data center. Ci sono n città in Uragania, ma sfortunatamente non ci sono data center di entrambi i giganti in nessuna città. Pertanto, per formare un canale sicuro, dovranno essere posate linee di comunicazione a lunga distanza.
Gli specialisti delle aziende hanno identificato m coppie di città che possono essere collegate mediante la posa di un segmento di canale di comunicazione e hanno stimato il costo di creazione di tale segmento per ciascuna di queste coppie.
Il canale risultante può essere costituito da diversi segmenti. Deve iniziare in una delle città in cui si trova il data center della prima azienda, può passare per città intermedie e deve terminare nella città in cui si trova il data center della seconda azienda.
Ora è necessario determinare il costo minimo di un canale sicuro che colleghi i data center di due aziende.
Inserimento:
La prima riga contiene gli interi n e m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) — il numero di città e il numero di coppie di città che possono essere collegate da un segmento di collegamento. La seconda riga contiene n numeri interi ai (0 ≤ a
i ≤ 2). Se a
i = 0, allora non esiste alcun data center di nessuno dei giganti nella i-esima città. Se ai = 1, allora il data center "Laim.UR" si trova nella i-esima città, e se a
i = 2, allora il data center "Xenda" si trova nella i- la città; . È garantito che tra questi numeri ce ne sia almeno uno uno e uno due. Ognuna delle m righe successive contiene tre numeri interi — s
i , t
i e c
i , il che significa che le città s
i e t
i (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>) può essere connesso da un segmento di collegamento di costo ci (1 ≤ ci ≤ 105 ). Ogni coppia di città può essere collegata al massimo da un segmento di canale.
Uscita:
Se è possibile connettere due data center di diversi giganti di Internet con un canale di comunicazione sicuro, stampare tre numeri nel file di output: x, y e d, il che significa che è possibile stabilire un canale di comunicazione tra le città x e y con un costo totale di d. Nella città x dovrebbe esserci un data center "Laim.UR", nella città y — centro dati «Xenda». Se ci sono diverse risposte ottimali, stampane una qualsiasi. Se non è possibile disegnare il canale richiesto, stampare −1.
Esempi
| # |
Input |
Uscita |
| 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 |
Spiegazione
Nel primo esempio, è ottimale costruire un canale di comunicazione da due segmenti: 3 − 2 e 2 .meno; 4.