Problem
A la luz de las recientes noticias de escuchas telefónicas, los dos gigantes de Internet de línea dura Uragania Laim.UR y "xenda" decidió firmar un acuerdo para establecer un canal de comunicación seguro entre los centros de datos de cada uno. Hay n ciudades en Uragania, pero, desafortunadamente, no hay centros de datos de ambos gigantes en ninguna ciudad. Por lo tanto, para formar un canal seguro, se deberán establecer líneas de comunicación de larga distancia.
Los especialistas de las empresas identificaron m pares de ciudades que se pueden conectar mediante la colocación de un segmento de canal de comunicación y estimaron el costo de crear dicho segmento para cada uno de estos pares.
El canal resultante puede constar de varios segmentos. Debe comenzar en una de las ciudades donde se encuentra el centro de datos de la primera empresa, puede pasar por ciudades intermedias y debe terminar en la ciudad donde se encuentra el centro de datos de la segunda empresa.
Ahora es necesario determinar el costo mínimo de un canal seguro que conecte los centros de datos de dos empresas.
Entrada:
La primera línea contiene números enteros n y m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) — el número de ciudades y el número de pares de ciudades que se pueden conectar mediante un segmento de enlace. La segunda línea contiene n enteros ai (0 ≤ a
i ≤ 2). Si a
i = 0, entonces no hay centro de datos de ninguno de los gigantes en la i-ésima ciudad. Si ai = 1, entonces el centro de datos "Laim.UR" está ubicado en la i-ésima ciudad, y si a
i = 2, entonces el centro de datos "Xenda" está ubicado en la i-ésima ciudad. ª ciudad; . Se garantiza que entre estos números hay al menos uno uno y uno dos. Cada una de las siguientes m líneas contiene tres números enteros — s
i , t
i y c
i , lo que significa que las ciudades s
i y t
i (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>) se puede conectar mediante un segmento de enlace de costo ci (1 ≤ ci ≤ 105 ). Cada par de ciudades se puede conectar como máximo mediante un segmento de canal.
Salida:
Si es posible conectar dos centros de datos de diferentes gigantes de Internet con un canal de comunicación seguro, imprima tres números en el archivo de salida: x, y y d, lo que significa que es posible establecer un canal de comunicación entre las ciudades x e y con un costo total de d. En la ciudad x debe haber un centro de datos "Laim.UR", en la ciudad y — centro de datos «Xenda». Si hay varias respuestas óptimas, imprima cualquiera. Si es imposible dibujar el canal requerido, imprima −1.
Ejemplos
| # |
Entrada |
Salida |
| 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 |
Explicación
En el primer ejemplo, es óptimo construir un canal de comunicación a partir de dos segmentos: 3 − 2 y 2 .menos; 4.