Mario and Luigi

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
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 multiedges are allowed to exist.
Input
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two integers N and M denoting number of vertexes 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 vertexes and cost of edge.
Output
For each test case, output M lines containing the difference between Mario's and Luigi's points after adding the ith 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.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N, M ≤ 10^{5}
 1 ≤ u, v ≤ N
 1 ≤ c ≤ 10^{9}
 Self loops and multiple edges are allowed.
Subtasks
 Subtask 1 (10 points): 1 ≤ N ≤ 10, 1 ≤ M ≤ 100
 Subtask 2 (40 points): 1 ≤ N, M ≤ 2000
 Subtask 3 (50 points): original constraints
Example
Input: 1 5 4 1 2 1 1 3 1 1 4 1 1 5 1 Output: 0 1 1 2
Author:  furko 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/FURGRAPH 
Tags  april16 furko graphs hard segmenttree treaps 
Date Added:  14122015 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions