Dynamic Class Affection

There are \(n\) students in a class with IDs from \(1\) to \(n\). Each student \(i\) has an affection rating toward every other student \(j\) (with \(i \neq j\)), and initially every rating is \(0\). The affection rating is always a nonnegative integer.

Then, \(m\) events occur sequentially. Each event is described by three integers \(a\), \(b\), and \(d\), which means the affection rating of student \(a\) for student \(b\) changes by \(d\) (it increases if \(d > 0\) or decreases if \(d < 0\)). It is guaranteed that after every change, the rating remains a nonnegative integer.

After each event, output the maximum affection rating among all pairs \((p, q)\) with \(p \neq q\). Note that the affection rating is one‐directional; i.e. the rating from \(p\) to \(q\) may not equal the rating from \(q\) to \(p\).

inputFormat

The first line contains two integers \(n\) and \(m\) (number of students and number of events).

Each of the following \(m\) lines contains three integers \(a\), \(b\), and \(d\), representing an event in which student \(a\)'s affection rating for student \(b\) changes by \(d\).

outputFormat

Output \(m\) lines. The \(i\)th line should contain a single integer: the maximum affection rating among all pairs after the \(i\)th event.

sample

3 3
1 2 5
2 3 4
1 2 -3

5
5
4