C. Car Trip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a certain region, there are $$$n$$$ cities. Some pairs of cities are connected by bidirectional roads. Any two cities are connected directly by no more than one road.

Student Vasily wants to drive from city 1 to city $$$n$$$ in his car. He has already calculated how many liters of gasoline are needed to travel each road in his car.

Gas stations are only available in cities. However, Vasily can take as many canisters as he wants, so he can refuel any amount of gasoline in any city. Initially, he is at a gas station in the first city, and he has zero liters of gasoline.

The price per liter of gasoline may vary in different cities. Determine the minimum amount of money Vasily needs to spend to get from city 1 to city $$$n$$$. Also, determine his route and how many liters of gasoline he should buy in each city along the way.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ — the number of cities and the number of roads ($$$2 \le n \le 1000$$$, $$$0 \le m \le 10000$$$).

The next line contains $$$n$$$ integers $$$c_i$$$ — the cost of one liter of gasoline in each city ($$$1 \le c_i \le 100$$$).

The following $$$m$$$ lines contain information about the roads — triples of integers $$$u_i$$$, $$$v_i$$$, and $$$f_i$$$, where $$$u_i$$$ and $$$v_i$$$ are the cities connected by the respective road ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), and $$$f_i$$$ is the amount of gasoline required to travel this road ($$$1 \le f_i \le 100$$$).

Output

If it is possible to get from city 1 to city $$$n$$$, then output in the first line the minimum amount of money that must be spent on gasoline. In the second line, output the integer $$$k$$$ — the number of cities in the found route. In the following $$$k$$$ lines, output pairs of integers — the number of each city in order and the amount of gasoline that needs to be bought in that city. If there are multiple correct answers, output any.

If it is not possible to get from city 1 to city $$$n$$$, output -1.

Examples
Input
5 5
50 40 10 100 75
1 2 4
1 4 3
2 5 9
3 4 5
4 5 10
Output
550
5
1 8
4 0
3 15
4 0
5 0
Input
4 2
10 20 30 40
1 2 50
3 4 100
Output
-1
Note

The illustration for the first example:

Next to the vertices are the gasoline prices, and next to the edges are the consumption in liters. In the example, we refuel 8 liters in city 1, go to city 4, then go to city 3 for cheaper gasoline and refuel 15 liters there, return to city 4, and go to city 5.