Mario and Luigi are very lazy guys. These are not the guys from some game, these are the ones playing games all the time. Recently, they bought a new game named "Graph Vertices chooser".
The rules of this game are pretty simple. It's a two player game with each player taking alternating turns starting with Mario. You are given a weighed graph. All the vertices are initially unmarked. In each turn, a player chooses an unmarked vertex and mark it to red or black color (Mario marks red whereas Luigi marks black). The game ends when there is no any unmarked vertex left. After the end of the game, Mario's score will be weight of all the edges in graph such that both the end points of the edge are colored red. Similarly, score of Luigi is sum of weight of edges with both end points being black.
Mario would like to maximize difference between his and Luigi points, while Luigi would like to minimize the difference between Mario's and his score. Both player optimally.
Now, you are the one who decided to be the coach of both the players. You want to create many graphs for Mario and Luigi to train. For that, you decided to take a graph H of N vertices. Initially, there is no edge in graph H. One by one, you will add an edge in the graph H and ask the both the players to play on the newly created graph. You will add M such edges. For each of the M graphs, you have to tell the difference between points of Mario and Luigi at the end of the game, when they play the game on that graph. Note that self loops and multi-edges are allowed to exist.
Note : Difference of Mario's and Luigi's score is Mario's score - Luigi's score, which means it might be negative.
The first line contains two integers N and M denoting number of vertices and number of edges to be added by the coach.
Each of the next M lines contains description of each edge u, v, c, denoting two vertices and cost of edge.
Output M lines containing the difference between Mario's and Luigi's points after adding the i-th edge, for each i.
You should add edges one by one (with same order as they follows in input), and every time output the difference between points of Mario and Luigi at the end of each game.
- 1 ≤ N, M ≤ 105
- 1 ≤ u, v ≤ N
- 1 ≤ c ≤ 109
- Self loops and multiple edges are allowed.
- Subtask 1 (10 points): 1 ≤ N ≤ 10, 1 ≤ M ≤ 100
- Subtask 2 (40 points): 1 ≤ N, M ≤ 2000
- Subtask 3 (50 points): original constraints
1 2 1
1 3 1
1 4 1
1 5 1
furko from CodeChef. Testdata by Msia APIO Camp 2016 Training Team.