In light of recent wiretapping news, the two hardline internet giants Uragania Laim.UR and "Xenda" decided to sign an agreement on establishing a secure communication channel between each other's data centers. There are n cities in Uragania, but, unfortunately, there are no data centers of both giants in any city. Therefore, to form a secure channel, long-distance communication lines will have to be laid.
The specialists of the companies have identified m pairs of cities that can be connected by laying a communication channel segment and estimated the cost of creating such a segment for each of these pairs.
The resulting channel may consist of several segments. It must start in one of the cities where the data center of the first company is located, it can pass through intermediate cities and must end in the city where the data center of the second company is located.
Now it is necessary to determine the minimum cost of a secure channel connecting two companies' data centers.
Input:
The first line contains integers n and m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10
5 ) — the number of cities and the number of pairs of cities that can be connected by a link segment. The second line contains n integers ai (0 ≤ a
i ≤ 2). If a
i = 0, then there is no data center of any of the giants in the i-th city. If ai = 1, then the "Laim.UR" data center is located in the i-th city, and if a
i = 2, then the "Xenda" data center is located in the i-th city; . It is guaranteed that among these numbers there is at least one one and one two. Each of the next m lines contains three integers — s
i , t
i and c
i , which means that the cities s
i and t
i (1 ≤ s
i , t
i ≤ n, s
i != t
i< /sub>) can be connected by a link segment of cost ci (1 ≤ ci ≤ 105 ). Each pair of cities can be connected by at most one channel segment.
Output:
If it is possible to connect two data centers of different Internet giants with a secure communication channel, then print three numbers in the output file: x, y and d, meaning that it is possible to establish a communication channel between cities x and y with a total cost of d. In city x there should be a data center "Laim.UR", in city y — data center «Xenda». If there are several optimal answers, print any one. If it is impossible to draw the required channel, print −1.
Examples
| # |
Input |
Output |
| 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 |
Explanation
In the first example, it is optimal to build a communication channel from two segments: 3 − 2 and 2 .minus; 4.