协助

题目描述

上回说到伊娜三人和拉迪亚在一个藏宝洞穴寻找“龙王神力”的组件之一“龙翼袍”，他们发现开启机关需要雷神之盔纹理勾画出的一个电路图。伊娜和雷尔对物理不太精通，拉迪亚是魔族，只懂魔理。好在弗里曼是皇族出身，从小接受9年制义务教育，理工科一流。他掏出《5年高考3年模拟》翻了翻，很快就找到了问题的关键

电路共有n个节点1..n，每个节点有一个电势Ui。并且这些电势值有满足如下一些条件

1.由于最低电势点接地，所有Ui都是非负整整

2.某些节点i,j之间电势之差为固定的常数

你必须使用基尔霍夫第一/第二定理求出电势的值（←此句为开玩笑）。在满足如上条件的基础上，要求所有电势之和最小。弗里曼虽然破解了的方法，但是手算的速度太慢了，所以只能请求你的帮助。而伊娜出于好(wu)奇(liao)，还希望你能在线给出答案~~

输入输出格式
输入格式
第1行2个正整数n,m
后面m行每行3个正整数i,j,D，表示i点的电势比j点高D（Ui-Uj=D）

输出格式
包含不超过m行，每行一个非负整数。每输入一组(i,j,D)，伊娜都要求你输出符合当前已给出的约束条件下，电势总和的最小值。如果输入某一组(i,j,D)后，发生了矛盾情况，则输出终止。即如果第k组输入第一次出现了矛盾，则输出共k-1行；如果一直没有矛盾，那么输出就有m行

输入输出样例
输入样例#1:

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

输出样例#1:

1
3
4
10

说明
20%的数据，1≤n,m≤10
60%的数据，1≤n,m≤2000
100%的数据，1≤n,m≤100000，1≤i,j≤n，0≤D≤10000