Bill's Binoculars

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type

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 ith event, xi people leave House ai and enter House bi. 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

2N5×105

1K5×105

1ai,biN

1xi109

aibi

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, ai, bi, and xi, indicating that xi people went from House ai to House bi.

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

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:

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

Comments


  • 1
    mrjones  commented on June 5, 2022, 8:59 p.m.

    Numbers possibly going up to 109 is the key information here.