Module: Dijkstra-Algorithmus

Problem

Angesichts der jüngsten Nachrichten über das Abhören von Kommunikationskanälen sind die beiden unversöhnlichen Internetgiganten Hurrikan «Laim.UR» und «Xenda» haben beschlossen, eine Vereinbarung zu unterzeichnen, um einen sicheren Kommunikationskanal zwischen den Rechenzentren des jeweils anderen zu etablieren. Es gibt einen Hurrikan von n Städten, aber leider gibt es in keiner Stadt die Rechenzentren beider Giganten. Daher müssen Fernkommunikationsleitungen verlegt werden, um einen geschützten Kanal zu bilden.
Die Spezialisten der Unternehmen haben die m-Paare von Städten identifiziert, die durch Verlegen eines Kommunikationskanalsegments verbunden werden können, und die Kosten für die Erstellung eines solchen Segments für jedes dieser Paare geschätzt.

Der resultierende Kanal kann aus mehreren Segmenten bestehen. Es muss in einer der Städte beginnen, in denen sich das Rechenzentrum des ersten Unternehmens befindet, kann durch die Zwischenstädte gehen und muss in der Stadt enden, in der sich das Rechenzentrum des zweiten Unternehmens befindet.
Jetzt müssen Sie die minimalen Kosten für einen sicheren Kanal ermitteln, der die beiden Rechenzentren der Unternehmen verbindet.

Eingabe:
Die erste Zeile enthält ganze Zahlen n und m (2 ≤ n ≤ 5 000, 1 ≤ m ≤ 10⁵ ) — Anzahl der Städte und die Anzahl der Städtepaare, die durch ein Kommunikationssegment verbunden werden können. Die zweite Zeile enthält n ai-Ganzzahlen (0 ≤ a_i ≤ 2). Wenn a_i = 0 ist, gibt es in der i-Stadt kein Rechenzentrum für einen der Giganten. Wenn ai = 1 ist, gibt es ein Rechenzentrum in der i-Stadt «Laim.UR», und wenn a_i = 2 ist, dann befindet sich das Datenzentrum von «Xenda» in der i. Stadt. Es ist garantiert, dass es mindestens eine Einheit und eine Zwei unter diesen Zahlen gibt. In jeder der folgenden m Zeilen befinden sich drei ganze Zahlen: s_i , t_i und c_i , was bedeutet, dass die Städte s_i und t_i sind (1 ≤ s_i , t_i ≤ n, s_i != t_i) kann mit einem ci-Wert-Kanalsegment verbunden werden (1 ≤ c_i ≤ 10⁵ ). Jedes Städtepaar kann mit maximal einem Kanalsegment verbunden werden.

Ausgabe:
Wenn Sie möglicherweise zwei Datenzentren verschiedener Internetgiganten mit einem sicheren Kommunikationskanal verbinden, geben Sie in der Ausgabedatei drei Zahlen aus: x, y und d, was bedeutet, dass es möglich ist, einen Kommunikationskanal mit einem Gesamtwert von d zwischen den Städten x und y zu führen.UR», in der Stadt y — ist das Rechenzentrum von «Xenda». Wenn es mehrere optimale Antworten gibt, geben Sie eine aus. Wenn der gewünschte Kanal nicht ausgeführt werden kann, geben Sie −1 aus.

Beispiele

№	Eingabe	Ausgabe
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

Erklärung
Im ersten Beispiel ist es am besten, einen Kommunikationskanal aus zwei Segmenten zu erstellen: 3 − 2 und 2 − 4.