시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 20 | 6 | 5 | 26.316% |
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$.
4 4 1 2 1 2 3 2 3 4 3 1 4 4
7 6 6 8