24657번 - Edges, Colors and MST 다국어

There is an undirected simple connected graph $G$ with $N$ vertices and $M$ edges. The vertices of $G$ are numbered from 1 to $N$, and the edges are numbered from 1 to $M$. Edge $i$ connects vertices $u_i$ and $v_i$.

Given is a sequence $C = (c_1, c_2, \ldots, c_M)$ of length $M$, consisting of 0s and 1s. Edge $i$ is painted blue when $c_i=0$, and is painted red when $c_i=1$. The edges are colored in such a way that there are exactly $N-1$ red edges and they are forming a spanning tree of $G$.

Find the lexicographically smallest permutation $P = (p_1, p_2, \ldots, p_M)$ that satisfies the following condition: if, for each $i$, the weight of edge $i$ is $p_i$, then all the edges used in the minimal spanning tree of $G$ are red.

Note that the minimal spanning tree of $G$ is uniquely determined under those conditions.

The first line of input contains two integers $N$ and $M$: the number of vertices and edges in graph $G$, respectively ($2 \le N \le 2 \cdot 10^5$, $N-1 \le M \le 2 \cdot 10^5$).

The following $M$ lines contain descriptions of the edges. Each description contains three integers $a_i$, $b_i$ and $c_i$ ($1 \le a_i, b_i \le N$, $0 \le c_i \le 1$): the vertices that are connected by this edge and the color of the edge (red if $c_i=1$ and blue otherwise).

You may assume that there are no multiple edges nor loops, that the given graph is connected, and that the red edges are forming a spanning tree of the given graph.

Print $M$ integers that form the lexicographically smallest permutation $P$ that satisfies the following condition: if, for each $i$, the weight of edge $i$ is $p_i$, then all the edges used in the minimal spanning tree of $G$ are red.