Problem I
The Council

Today is the day of the octennial meeting of the Council of Atrebla. To start off the meeting, the Council members spent sixteen minutes throwing darts as a means to quantify the intrinsic value of each town in Atrebla as a single integer. With this information the Council intends to change the amount of funding that each town receives to prioritize those that are more intrinsically valuable. However, having just spent all the remaining spare funding on a dartboard, it was proclaimed that the sum of the funding assigned within any subset of towns must not exceed the total capacity of roads between that subset of the towns and the rest of Atrebla. Of course, there aren’t any roads between all of Atrebla and none of Atrebla, so the proclamation ensures that money is simply redistributed between the towns and no external funding is required. On this note the Council adjourned—entrusting you with implementing their scheme.

Atrebla contains $n$ towns, and has $m$ bidirectional roads between the towns. Each town has an intrinsic value $v_ i$ and each road has some capacity $c_ j$. No road has both endpoints at the same town and there is at most one road between each pair of towns. You are to assign some value $x_ i$ to each town indicating how much funding that town should receive. Note that some of the $x_ i$ may be negative, indicating that town $i$ owes money. Your goal is to produce an assignment $x$ that maximizes the value $\sum _{i=1}^ n v_ ix_ i$. However, for every subset $S$ of towns, the sum of funding $\sum _{i\in S}x_ i$ cannot exceed the total capacity of roads with one endpoint in $S$ and the other endpoint outside of $S$.

Input

The first line contains two integers $n$ and $m$, where $2\le n\le 10^5$, $1\le m\le 10^5$. The next $m$ lines contain three integers $a_ j$, $b_ j$ and $c_ j$ with $1\le a_ j,b_ j\le n$ and $1\le c_ j\le 10^6$ indicating that there is a road between towns $a_ j$ and $b_ j$ with capacity $c_ j$. The final $n$ lines contain integers $v_1,\dots ,v_ n$, where $0\le v_ i\le 10^6$.

Output

The first line of output should contain the maximum attainable value $\sum _{i=1}^ n v_ ix_ i$. The second line should contain values $x_1,\dots ,x_ n$ which attain the maximum. If there are multiple solutions, output the lexicographically largest solution.

3 2
1 2 6
2 3 9
20
10
30

240
6 -15 9

5 7
1 2 3
2 3 4
3 4 5
4 5 6
1 5 7
2 5 8
3 5 9
4
3
1
1
5

94
-4 -7 -8 -11 30