Problem
最近の盗聴ニュースに照らして、2 つの強硬派インターネットの巨人 Uragania Laim.URそして「ゼンダ」は、互いのデータ センター間に安全な通信チャネルを確立するための契約に署名することを決定しました。ウラガニアには n 個の都市がありますが、残念ながら、どの都市にも両方の巨人のデータセンターはありません。したがって、安全なチャネルを形成するには、長距離通信回線を敷設する必要があります。
企業の専門家は、通信チャネル セグメントを敷設することによって接続できる都市の m ペアを特定し、これらのペアごとにそのようなセグメントを作成するコストを見積もりました。
結果のチャネルは、複数のセグメントで構成される場合があります。最初の会社のデータ センターがある都市の 1 つで開始し、途中の都市を通過して、2 番目の会社のデータ センターがある都市で終了する必要があります。
ここで、2 つの企業のデータ センターを接続する安全なチャネルの最小コストを決定する必要があります。
入力:
最初の行には整数 n と m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) — が含まれます。リンク セグメントで接続できる都市の数と都市のペアの数。 2 行目には n 個の整数 ai (0 ≤ a
i ≤ 2) が含まれます。 a
i = 0 の場合、i 番目の都市にはどの巨人のデータセンターもありません。 ai = 1 の場合、「Laim.UR」データセンターは i 番目の都市にあり、a
i = 2 の場合、「Xenda」データセンターは i 番目の都市にあります。番目の都市; .これらの数の中には、少なくとも 1 つと 1 つ 2 つがあることが保証されています。次の m 行のそれぞれには、3 つの整数が含まれています。 s
i 、 t
i 、および c
i 、つまり都市 s
i および t
i (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>) は、コスト ci (1 ≤ ci ≤ 105 ) のリンク セグメントで接続できます。都市の各ペアは、最大で 1 つのチャネル セグメントで接続できます。
出力:
異なるインターネット大手の 2 つのデータ センターを安全な通信チャネルで接続できる場合、出力ファイルに x、y、d の 3 つの数字を出力します。これは、都市 x と y の間で通信チャネルを確立できることを意味しますdの総コスト。市 x にはデータセンター "Laim.UR" があり、市 y には — があります。データセンター「Xenda」。最適な答えが複数ある場合は、いずれかを出力します。必要なチャネルを描画できない場合は、−1 を出力してください。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 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 |
説明
最初の例では、2 つのセグメントから通信チャネルを構築するのが最適です。 2 と 2 .マイナス; 4.