Traveler Nobita

Time Limit: 2 Seconds
Memory Limit: 65536 KB

One day, Nobita used a time machine and went back to 1000 AD. He found that there are *N* cities in the kingdom he lived. The cities are numbered from 0 to *N* - 1. Before 1000 AD., there are no roads between any two cities. The kingdom will build one road between two cities at the beginning of each year starting from 1000 AD. There might be duplicated roads between two cities being built by the kingdom. You can assume that building a road takes no time.

At the beginning of every year, after the new road is built, Nobita will try to make a schedule to travel around all cities within that year. The travel should both begin at and end at the capital city - city_{0}. Every time Nobita arrived at a city *i*, he will spent *t1*_{i} days in that city, regardless of how many times he had come to the city. Of course he wouldn't need to spend any time in the capital city (that is to say, *t1*_{0} is always 0). And *t2*_{i} hours is required to pass road #*i*. Note that to pass each road, a passport of that road is required. And the kingdom limits that one person can only have no more than *N* - 1 passports of roads each year.

You are given information about the roads built in *M* years. Please find out the minimum time Nobita needed to complete his traveling schedule.

#### Input

There are multiple cases. The first line of a test case contains two integers, *N* (2 ≤ *N* ≤ 200) and *M* (1 ≤ *M* ≤ 10000). The next line contains *N* integers, indicating *t1*_{0} ... *t1*_{n - 1}. (0 ≤ *t1*_{i} ≤ 50) The next *M* lines, the *i*^{th} (0 ≤ *i* < *M*) line of this section contains three integers, *u*_{i}, *v*_{i}, *t2*_{i}, (0 ≤ *u*_{i}, *v*_{i} < N; 0 ≤ *t2*_{i} ≤ 5000),
indicating that in year *1000 + i* AD., a road will be built between city *u*_{i} and city *v*_{i}. *t1*_{i} and *t2*_{i} have been described above.

#### Output

For each case, you should output *M* lines. For the *i*^{th} line, if Nobita can make a schedule in year *1000 + i*, output the minimal days he can finish that schedule, rounded to two decimal digits. Otherwise output -1. There should be a blank line after each case.

#### Sample Input

5 6
0 5 2 5 4
0 1 1
0 2 2
0 3 5
3 4 2
2 4 4
1 2 1

#### Sample Output

-1
-1
-1
21.83
19.00
19.00

Author:

**XU, Shicheng**
Contest:

**ZOJ Monthly, December 2010**
Submit
Status