Description

糖糖给你出了一个没有自环和重边的无向权图。图包含n个顶点和m条边。

对于每条边(u, v)，糖糖想让你求包含这条边(u, v)的生成树的最小可能权值。

生成树的权值是生成树中所有边的权值之和。

Format

Input

第一行包含两个整数n和m(1<=n<=2e5,n - 1<=m<=2e5)-表示图中的顶点数和边数。

下m行每一行包含三个整数ui、vi、wi(1<=ui, vi<=n, ui != vi, 1<=wi<=1e9)-表示第i条边的端点及其权值。

Output

输出m行。第i行的答案代表包含第i条边的生成树的最小权值。

按照它们出现在输入中的顺序，这些边从1到m进行编号。

Samples

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

9
8
11
8
8
8
9

Hint