Problem
À la lumière des dernières nouvelles sur les écoutes téléphoniques, les deux géants de l'internet pur et dur Uragania Laim.UR et "Xenda" a décidé de signer un accord sur l'établissement d'un canal de communication sécurisé entre les centres de données de l'autre. Il y a n villes en Uragania, mais, malheureusement, il n'y a pas de centres de données des deux géants dans aucune ville. Par conséquent, pour former un canal sécurisé, des lignes de communication longue distance devront être posées.
Les spécialistes des entreprises ont identifié m paires de villes qui peuvent être connectées en posant un segment de voie de communication et ont estimé le coût de création d'un tel segment pour chacune de ces paires.
Le canal résultant peut être composé de plusieurs segments. Elle doit débuter dans l'une des villes où se trouve le centre de données de la première entreprise, elle peut passer par des villes intermédiaires et doit se terminer dans la ville où se trouve le centre de données de la deuxième entreprise.
Il faut maintenant déterminer le coût minimum d'un canal sécurisé reliant les centres de données de deux entreprises.
Saisie :
La première ligne contient des entiers n et m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) — le nombre de villes et le nombre de paires de villes pouvant être reliées par un segment de liaison. La deuxième ligne contient n entiers ai (0 ≤ a
i ≤ 2). Si a
i = 0, alors il n'y a aucun centre de données d'aucun des géants dans la ième ville. Si ai = 1, alors le centre de données "Laim.UR" est situé dans la ième ville, et si a
i = 2, alors le centre de données "Xenda" est situé dans la i- ème ville ; . Il est garanti que parmi ces nombres il y en a au moins un un et un deux. Chacune des m lignes suivantes contient trois entiers — s
i , t
i et c
i , ce qui signifie que les villes s
i et t
i (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>) peut être connecté par un segment de lien de coût ci (1 ≤ ci ≤ 105 ). Chaque paire de villes peut être connectée par au plus un segment de canal.
Sortie :
S'il est possible de connecter deux centres de données de géants de l'Internet différents avec un canal de communication sécurisé, alors imprimez trois nombres dans le fichier de sortie : x, y et d, ce qui signifie qu'il est possible d'établir un canal de communication entre les villes x et y avec un coût total de d. Dans la ville x, il devrait y avoir un centre de données "Laim.UR", dans la ville y — centre de données «Xenda». S'il y a plusieurs réponses optimales, écrivez-en une. S'il est impossible de tracer le canal requis, écrivez &moins;1.
Exemples
| # |
Entrée |
Sortie |
| 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 |
Explication
Dans le premier exemple, il est optimal de construire un canal de communication à partir de deux segments : 3 − 2 et 2 .moins ; 4.