Bill recently got a hold of a fresh new pair of binoculars. Of course, there is just one thing left to do: spy on his neighbours!

Across the street, Bill sees ~N~ houses laid out in a row. During his spy session, a total of ~K~ events occur. On the ~i^\text{th}~ event, ~x_i~ people leave House ~a_i~ and enter House ~b_i~. Intrigued by this, Bill decides to keep track of all of these events. At the end, he wants to figure out the minimum number of people that must exist on that street.

Constraints

~2 \le N \le 5 \times 10^5~

~1 \le K \le 5 \times 10^5~

~1 \le a_i, b_i \le N~

~1 \le x_i \le 10^9~

~a_i \ne b_i~

Input Specification

The first line contains two space-separated integers ~N~ and ~K~, the number of houses, and number of events, respectively.

The next ~K~ lines of input contain three space-separated integers, ~a_i~, ~b_i~, and ~x_i~, indicating that ~x_i~ people went from House ~a_i~ to House ~b_i~.

Output Specification

On the first line, output the minimum number of people in total that must exist on the street.

On the second line, output ~N~ space-separated integers, describing the number of people in each house prior to the events, such that the total number of people is minimized. If there are multiple ways of doing this, output any.

Sample Input

4 3
1 2 3
2 4 5
4 1 1

Sample Output

5
3 2 0 0

Explanation

The number of people in each house between each event would be:

• ~[3, 2, 0, 0]~ (initial count)
• ~[0, 5, 0, 0]~ (1st event)
• ~[0, 0, 0, 5]~ (2nd event)
• ~[1, 0, 0, 4]~ (3rd event)