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
houses laid out in a row. During his spy session, a total of
events occur. On the
event,
people leave House
and enter House
. 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](//static.dmoj.ca/mathoid/3b859aca724de268a15cb2b7783ee7cb65c03f68/svg)
![1 \le K \le 5 \times 10^5](//static.dmoj.ca/mathoid/01340f19ee9e27f3ae265508922996863180242c/svg)
![1 \le a_i, b_i \le N](//static.dmoj.ca/mathoid/c4fac0f7cec982e4878d958cfd895d1f620b884e/svg)
![1 \le x_i \le 10^9](//static.dmoj.ca/mathoid/d7952275d5a820eef9cfc0f61c3657e085921afe/svg)
![a_i \ne b_i](//static.dmoj.ca/mathoid/3be3e8a8c4d7a89e67e44c7e3704191adb2f513d/svg)
Input Specification
The first line contains two space-separated integers
and
, the number of houses, and number of events, respectively.
The next
lines of input contain three space-separated integers,
,
, and
, indicating that
people went from House
to House
.
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
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
Copy
4 3
1 2 3
2 4 5
4 1 1
Sample Output
Copy
5
3 2 0 0
Explanation
The number of people in each house between each event would be:
(initial count)
(1st event)
(2nd event)
(3rd event)
Comments
Numbers possibly going up to![10^9](https://static.dmoj.ca/static/blank.b44917055649.gif)
is the key information here.