import java.io.*;
import java.lang.reflect.Array;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

//Beispielcode zur Orientierung für Übungsblatt 8
public class Kruskal {

    // Funktion zum Einlesen eines Files
    public static ArrayList<String> read(String fileName) {

        ArrayList<String> data = new ArrayList<>();

        try {
            BufferedReader reader = new BufferedReader(
                    new FileReader(fileName));

            String line = "";

            while (line != null) {

                line = reader.readLine();

                if (line != null) {
                    data.add(line);
                }

            }
            reader.close();

        } catch (Exception e) {
            e.printStackTrace();
        }

        return data;
    }


    // Funktion zum Schreiben in einen File
    public static void write(String fileName, ArrayList<?> data) {
        try {
            BufferedWriter writer = new BufferedWriter(
                    new FileWriter(fileName));

            for (int i = 0; i < data.size(); i++)
                writer.write(data.get(i).toString() + "\n");

            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    // Kantenklasse
    private static class Edge implements Comparable<Edge> {

        int s, t, c;
        G graph;

        Edge(G g, int s, int t, int c) {
            this.s = s;
            this.t = t;
            this.c = c;
            this.graph = g;
        }


        Edge() {

            s = -1;
            t = -1;
            c = -1;
        }

        public String toString() {

            String sedge = "" + s + " " + t + " " + c;
            return sedge;
        }

        @Override
        public int compareTo(Edge e) {
            if (e != null) {
                return Integer.compare(this.c, e.c);
            }
            throw new ClassCastException("Objects is null");
        }
    }

    // Knotenklasse
    private static class Node {

        int ID;

        float lat, lon;

        ArrayList<Edge> outwardEdge, inwardEdge;


        Node(int ID, float lat, float lon) {

            this.ID = ID;
            this.lat = lat;
            this.lon = lon;
            outwardEdge = new ArrayList<Edge>();
            inwardEdge = new ArrayList<Edge>();
        }


        public String toString() {

            String snode = "" + ID + " " + lat + " " + lon;
            return snode;
        }

    }


    // Graphklasse
    private static class G {
        Node[] nodes;

        ArrayList<Edge> edges;

        //Konstruktor
        G(ArrayList<String> data) {

            //Einlesen der Knoten und Kanten
            int n = Integer.parseInt(data.get(0));
            int m = Integer.parseInt(data.get(1));

            nodes = new Node[n];
            edges = new ArrayList<>();

            System.out.println("read graph with " + n + " nodes and " + m + " edges");


            for (int i = 2; i < n + 2; i++) {
                String[] vpr = null;
                vpr = data.get(i).split("\\s+");
                float lat = Float.parseFloat(vpr[0]);
                float lon = Float.parseFloat(vpr[1]);
                Node node = new Node(i - 2, lat, lon);
                nodes[i - 2] = node;
            }


            for (int i = n + 2; i < n + m + 2; i++) {
                String[] vpr;
                vpr = data.get(i).split("\\s+");
                int sourceNode, targetNode, cost;
                sourceNode = Integer.parseInt(vpr[0]);
                targetNode = Integer.parseInt(vpr[1]);
                cost = Integer.parseInt(vpr[2]);

                Edge edge = new Edge(this, sourceNode, targetNode, cost);
                nodes[sourceNode].outwardEdge.add(edge);
                nodes[targetNode].inwardEdge.add(edge);

                Edge bedge = new Edge(this, targetNode, sourceNode, cost);
                nodes[sourceNode].inwardEdge.add(bedge);
                nodes[targetNode].outwardEdge.add(bedge);

                edges.add(edge);
                edges.add(bedge);

            }

        }


        public List<Integer> kruskalMST() {
            UnionFind uf = new UnionFind(nodes.length);
            Collections.sort(edges);
            List<Edge> ePrime = new ArrayList<>();
            for (Edge e : edges) {
                if (uf.findSet(e.s) != uf.findSet(e.t)) {
                    ePrime.add(e);
                    uf.union(e.s, e.t);
                }
            }
            return ePrime.stream().map(e -> e.c).collect(Collectors.toList());
        }
    }

    public static class UnionFind {

        int[] refs;
        boolean[] reps;

        UnionFind(int n) {
            AtomicInteger counter = new AtomicInteger(-1);
            refs = IntStream.generate(counter::incrementAndGet).limit(n).toArray();
            reps = new boolean[n];
            Arrays.fill(reps, true);
        }

        private int findSet(int id) {
            // id already is a base reference
            if (reps[id]) {
                return id;
            } else {
                //recursively look for a base reference
                return findSet(refs[id]);
            }
        }

        public void union(int v, int w) {
            int rep = findSet(v);
            refs[rep] = w;
            reps[rep] = false;
        }
    }


    public static void main(String args[]) {
        System.out.println("lel");
        long start = System.currentTimeMillis();
        if (args.length < 2)
            return;

        ArrayList<String> data = read(args[0]);
        G graph = new G(data);
        // Berechne Spannwald
        List<Integer> MSTedges = graph.kruskalMST();
        long end = System.currentTimeMillis();
        System.out.println("Time elapsed: " + (end - start) + "ms");
        write(args[1], new ArrayList<>(MSTedges));
		System.out.println("Here you go bb");

    }

}