Problem
À luz das recentes notícias de escutas telefônicas, os dois gigantes linha-dura da Internet Uragania Laim.UR e "Xenda" decidiu assinar um acordo para estabelecer um canal de comunicação seguro entre os centros de dados uns dos outros. Existem n cidades em Uragania, mas, infelizmente, não existem data centers de ambos os gigantes em nenhuma cidade. Portanto, para formar um canal seguro, linhas de comunicação de longa distância terão que ser estabelecidas.
Os especialistas das empresas identificaram m pares de cidades que podem ser conectadas estabelecendo um segmento de canal de comunicação e estimaram o custo de criar tal segmento para cada um desses pares.
O canal resultante pode consistir em vários segmentos. Deve iniciar em uma das cidades onde está localizado o datacenter da primeira empresa, pode passar por cidades intermediárias e deve terminar na cidade onde está localizado o datacenter da segunda empresa.
Agora é preciso determinar o custo mínimo de um canal seguro conectando os data centers de duas empresas.
Entrada:
A primeira linha contém inteiros n e m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) — o número de cidades e o número de pares de cidades que podem ser conectados por um segmento de link. A segunda linha contém n inteiros ai (0 ≤ a
i ≤ 2). Se a
i = 0, então não há data center de nenhum dos gigantes na i-ésima cidade. Se ai = 1, então o data center "Laim.UR" está localizado na i-ésima cidade, e se a
i = 2, então o data center "Xenda" está localizado na i- ª cidade; . É garantido que entre esses números haja pelo menos um um e um dois. Cada uma das próximas m linhas contém três números inteiros — s
i , t
i e c
i , o que significa que as cidades s
i e t
i (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>) pode ser conectado por um segmento de link de custo ci (1 ≤ ci ≤ 105 ). Cada par de cidades pode ser conectado por no máximo um segmento de canal.
Saída:
Se for possível conectar dois data centers de diferentes gigantes da Internet com um canal de comunicação seguro, imprima três números no arquivo de saída: x, y e d, o que significa que é possível estabelecer um canal de comunicação entre as cidades x e y com um custo total de d. Na cidade x deve haver um data center "Laim.UR", na cidade y — centro de dados «Xenda». Se houver várias respostas ótimas, imprima qualquer uma delas. Se for impossível desenhar o canal necessário, imprima &menos;1.
Exemplos
| # |
Entrada |
Saída |
| 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 |
Explicação
No primeiro exemplo, é ideal construir um canal de comunicação a partir de dois segmentos: 3 &menos; 2 e 2 .menos; 4.