시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 2 2 2 100.000%

문제

In this problem, we will consider weighted undirected graphs where all edges have positive weights.

We are given a weighted undirected graph $G$ which consists of $n$ vertices numbered from $1$ to $n$. Among the spanning trees of $G$, the MST (Minimum Spanning Tree) with metropolis vertex $i$ is the one that contains every possible edge with the metropolis (the vertex $i$) and minimizes the sum of edge weights in it. Let this edge weight sum be $S_i$. Your task is to calculate $S_i$ for every vertex $i$.

입력

The first line contains two integers $n$ and $m$: the number of vertices and edge in the graph, respectively ($1 \leq n \leq 10^5$, $n - 1 \leq m \leq 3 \times 10^5$).

Each of the following $m$ lines describes a single edge and contains three integers, $x$, $y$, and $c$ which mean that there is an edge between vertices $x$ and $y$ of weight $c$ ($1 \leq x < y \leq n$, $1 \leq c \leq 10^9$).

It is guaranteed that the given graph is connected, and there is at most one edge between every possible pair of vertices.

출력

Print $n$ lines. The $i$-th line must contain an integer $S_i$: the weight of the MST with metropolis vertex $i$.

예제 입력 1

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

예제 출력 1

7
6
6
8