19297번 - MST with Metropolis 출처다국어분류

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$.