ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Winter 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Happiness to People!

Time limit: 1.0 second
Memory limit: 64 MB
Every Santa Claus wants to surprise children with his presents. This year Santa Claus Petrovich wants to surprise children of remote Cuckooland. He is sure that in order to make a real impression he should choose a route without repeating towns. In order to bring as much happiness as possible, he plans to visit the most populated places. Petrovich took a map of Cuckooland and connected with lines some pairs of towns where, he's sure, people will wait for him. He decided not to fly between towns that are not connected. It turned out that if Petrovich can fly (using one or several flights) from town i to town j, then there is exactly one way to do this. Petrovich can start his trip in any of the towns.
Petrovich knows that when he arrives in town i, the population feels happiness Ai. And when Petrovich flies from town i to town j, he bestows happiness Cij. The same amount of happiness is bestowed if he flies from j to i. Help Santa Claus Petrovich to maximize the amount of happiness that he can bring to people.


The first line contains the number N (1 ≤ N ≤ 50000) of towns in Cuckooland and the number K of pairs of towns that are connected. The second line contains numbers Ai (i = 1..N); Ai ≤ 10000. Each of the following K lines contains three numbers a, b, c, which mean that when Petrovich flies from town a to town b he brings happiness c (ab; c ≤ 10000). All numbers in the input are whole and nonnegative.


The first line of the output must contain the maximal amount of happiness felt by the people of Cuckooland. The second line must contain the length L of the optimal route of Santa Claus Petrovich. The third line must contain the optimal route (L numbers separated with a space). If there are several answers, you may output any of them.


2 1
1 1
1 2 1
1 2
8 7
1 5 4 6 10 1 2 2
1 2 1
2 3 10
2 4 1
4 5 1
4 6 2
6 7 2
6 8 3
5 4 2 3
Problem Author: Alexander Toropov, special thanks to Alexander Ipatov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006
To submit the solution for this problem go to the Problem set: 1463. Happiness to People!