Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3461
Money Transfer

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Members of ACM/ICPC teams of Zhejiang University get various of prizes every year. And they will be awarded some money according to the prizes by the university.

An ACM/ICPC team consists of three students, one of which is the team leader. To simplify the work, the university will send money, which is awarded to a team, directly to the team leader. It is the team leader's responsibility to divide the money evenly among team members. Since there are several contests every year and a student can be in different teams in different contests, the "money transfer" job becomes more complex.

Transferring money from one student to another requires an available path. Since students live in different campuses and some of them may be traveling far away, there might be no paths between two students and the lengths of paths between different students may vary. Transferring money from one student to another with a selected path takes a cost equal to the length of that path. The cost has nothing to do with the amount of money being transferred.

For example, Alice needs to give some money to Bob. Alice can use a path that connecting she and Bob to go to Bob's then give him the money. This process requires a cost of the length of selected path. After the money is transferred, Alice returns to her place. A student always returns with no money carried and the returning process does not require any cost.

Given the lengths of paths among some students and the money each student get from the university or should get, your task is to calculate the minimal sum of cost needed to finish money transfer.


There are multiple test cases (about 20, most of which are small ones).

The first line of each case contains two integers N (2 ≤ N ≤ 16) and M (0 ≤ MN(N - 1) / 2). N is the number of ACM/ICPC team members and M is the number of available transferring paths between N students.

The second line contains N integers: a1, a2 ... aN (-1000 ≤ ai ≤ 1000). If ai is positive, student #i has ai RMB that should give to others. If ai is negative, student #i need to get |ai| RMB from others. If ai is zero, student #i doesn't need to receive or give money, however, he or she may act as a proxy helping transferring money.

It is guaranteed that a1 + a2 + ... + aN = 0.

Next M lines, each line contains three integers: p, q (0 ≤ p, q < N, p != q) and w (0 ≤ w ≤ 1000), indicating that there is a path with length w between student #p and student #q.

It is guaranteed that every unordered pair {p, q} in a line is unique among these M lines.

There is a blank line after a test case.


For each case, output the minimal cost in a line to finish money transfer. If there is no solution, output "Impossible" instead.

Sample Input

3 3
50 -20 -30
0 1 10
1 2 20
0 2 100

2 0
10 -10

Sample Output



For the first sample case, student #0 gives student #1 50 RMB, then student #1 gives student #2 30 RMB.

Author: WU, Jun
Contest: ZOJ Monthly, January 2011
Submit    Status