# Rooted Minimum Spanning Tree SOLUTIONS ROOTMST

Page Contents

## Rooted Minimum Spanning Tree SOLUTION OCTOBER CHALLENGE 2020

You are given a weighted simple undirected graph, vertex 1 is not an articulation point and connected to all other vertices.
For each K∈{1,2,…,N−1} you need to find the smallest weight of the spanning tree where the degree of vertex 1 is equal to K.
Input:
The first line of input contains two integers N,M: the number of vertices and edges in the graph.
Each of the next M lines contains three integers Ui,Vi,Wi (1≤Ui<Vi≤N), denoting an edge between vertices Ui and Vi with weight Wi.
It is guaranteed that the graph contains no multiple edges and vertex 1 is not an articulation point and its degree is equal to N−1.
Output:
Print N−1 integers: the smallest weight of the spanning tree where the degree of vertex 1 is equal to 1,2,…,N−1.
Constraints
2≤N≤100000
2N−3≤M≤200000
1≤Wi≤200000.
10 points : 2≤N≤5
10 points : 2≤N≤500
10 points : 2≤N≤10000
70 points : 2≤N≤100000
Sample Input:
4 5
1 2 1
1 3 1
1 4 1
2 3 2
3 4 2
Sample Output:
5 4 3
LOGIC WILL BE UPLOADED SOON STAY TUNE AND