在本题中，我们考虑所有边权均为正的加权无向图。

给定一个包含 $n$ 个顶点的加权无向图 $G$，顶点编号从 $1$ 到 $n$。在 $G$ 的所有生成树中，以“大都市顶点 $i$”（metropolis vertex $i$）为中心的最小生成树（MST）是指包含所有与该大都市（顶点 $i$）相连的边，并使生成树中边权之和最小的生成树。设该边权之和为 $S_i$。你的任务是计算每个顶点 $i$ 对应的 $S_i$。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示图中的顶点数和边数（$1 \le n \le 10^5$，$n - 1 \le m \le 3 \times 10^5$）。

接下来的 $m$ 行，每行描述一条边，包含三个整数 $x$、$y$ 和 $c$，表示顶点 $x$ 和 $y$ 之间存在一条权值为 $c$ 的边（$1 \le x < y \le n$，$1 \le c \le 10^9$）。

保证给定的图是连通的，且任意两个顶点之间最多只有一条边。

输出格式

输出 $n$ 行。第 $i$ 行包含一个整数 $S_i$，表示以顶点 $i$ 为大都市顶点的最小生成树的权值。

样例

输入 1

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

输出 1

7
6
6
8