| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 256 MB | 878 | 315 | 232 | 34.835% |
You are given an undirected weighted graph G with n nodes and m edges. Each edge is numbered from 1 to m.
Let Gi be an graph that is made by erasing i-th edge from G. Your task is to compute the cost of minimum spanning tree in Gi for each i.
The dataset is formatted as follows.
n m a1 b1 w1 ... am bm wm
The first line of the input contains two integers n (2 ≤ n ≤ 100,000) and m (1 ≤ m ≤ 200,000). n is the number of nodes and m is the number of edges in the graph. Then m lines follow, each of which contains ai (1 ≤ ai ≤ n), bi (1 ≤ bi ≤ n) and wi (0 ≤ wi ≤ 1,000,000). This means that there is an edge between node ai and node bi and its cost is wi. It is guaranteed that the given graph is simple: That is, for any pair of nodes, there is at most one edge that connects them, and ai ≠ bi for all i.
Print the cost of minimum spanning tree in Gi for each i, in m line. If there is no spanning trees in Gi, print "-1" (quotes for clarity) instead.
4 6 1 2 2 1 3 6 1 4 3 2 3 1 2 4 4 3 4 5
8 6 7 10 6 6
4 4 1 2 1 1 3 10 2 3 100 3 4 1000
1110 1101 1011 -1
7 10 1 2 1 1 3 2 2 3 3 2 4 4 2 5 5 3 6 6 3 7 7 4 5 8 5 6 9 6 7 10
27 26 25 29 28 28 28 25 25 25
3 1 1 3 999
-1