import java.util.*;
public class d5 {
    //并查集
    public static class bingchaji{
        public HashMap<node,node> fathermap;
        public HashMap<node,Integer> sizemap;
        public bingchaji(){
            fathermap=new HashMap<>();
            sizemap=new HashMap<>();
        }
        public node findefather(node x){
            Stack<node> s=new Stack<>();
            while(x!=fathermap.get(x)){
                s.add(x);
                x=fathermap.get(x);
            }
            while(!s.isEmpty()){
                node cur=s.pop();
                fathermap.put(cur,x);
            }
            return x;
        }
        public void makeset(Collection<node>nodes){
            if(nodes==null) return;
            for(node cur:nodes){
                fathermap.put(cur,cur);
                sizemap.put(cur,1);
            }
        }
        public boolean issame(node a,node b){
            return findefather(a)==findefather(b);
        }
        public void union(node a,node b){
            if(a==null||b==null) return;
            node fa=findefather(a);
            node fb=findefather(a);
            if(fa!=fb){
                int lena=sizemap.get(fa);
                int lenb=sizemap.get(fb);
                node big=lena>=lenb?a:b;
                node small=big==a?b:a;
                fathermap.put(small,big);
                sizemap.put(big,lena+lenb);
                sizemap.remove(small);
            }
        }
    }
    public static class edgecom implements Comparator<edge>{
        @Override
        public int compare(edge o1, edge o2) {
            return o1.weight-o2.weight;//
        }
    }//比较器
    public static List<edge>K(graph g){
        bingchaji u=new bingchaji();
        u.makeset(g.nodes.values());
        List<edge> ans=new ArrayList<>();
        PriorityQueue<edge> q=new PriorityQueue<>(new edgecom());
        for(edge e:g.edges){
            q.add(e);
        }
        while(!q.isEmpty()){
            edge cure=q.poll();
            if(!u.issame(cure.from,cure.to)){
                ans.add(cure);
                u.union(cure.from,cure.to);
            }
        }
        return ans;
    }
}