using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace ConsoleApp2
{
    struct Krawedz
    {
        public int u;
        public int v;
        public int priorytet;
    }
    class PriorityQueue
    {
        public List<Krawedz> kopiec;
        public PriorityQueue()
        {
            kopiec = new List<Krawedz>();
        }
        public void Dodaj(Krawedz x)
        {
            kopiec.Add(x);
            int syn = kopiec.Count - 1; //syn - ostatni element w tablicy = x

            while (syn > 0)
            {
                int rodzic = (syn - 1) / 2;
                if (kopiec[rodzic].priorytet <= x.priorytet) break; // jeśli rodzic ma mniejszy priorytet od x
                                                                    // przerywamy - kopiec jest dobrze utowrzony

                kopiec[syn] = kopiec[rodzic];   // jeśli nie przywracamy strukturę kopca
                syn = rodzic;
            }

            if (kopiec.Count > 0) kopiec[syn] = x; //znaleźliśmy miejsc x w kopcu
        }

        public void Wypisz()
        {
            foreach (Krawedz i in kopiec)
            {
                Console.WriteLine("Krawedzie: " + i.u + "-" + i.v + " Waga: " + i.priorytet);
            }
        }
        public void Zdejmij()
        {

            Krawedz liść = kopiec[kopiec.Count - 1];
            kopiec.RemoveAt(kopiec.Count - 1);

            int i = 0;
            while (i * 2 + 1 < kopiec.Count)
            {
                int syn1 = i * 2 + 1;
                int syn2 = i * 2 + 2;
                int rodzic = syn2 < kopiec.Count && kopiec[syn2].priorytet < kopiec[syn1].priorytet ? syn2 : syn1;
                //indeks rodzic wskazuje na jego mniejszego syna

                if (kopiec[rodzic].priorytet >= liść.priorytet) break;
                kopiec[i] = kopiec[rodzic];
                i = rodzic;
            }

            if (kopiec.Count > 0) kopiec[i] = liść;
        }

        public Krawedz Korzen()
        {
            if (kopiec.Count == 0) throw new InvalidOperationException("Queue is empty.");
            return kopiec[0];
        }

        public int Ilosc()
        {
            return kopiec.Count;
        }
        public void Clear()
        {
            kopiec.Clear();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            PriorityQueue kolejka = new PriorityQueue();
            string[] line = System.IO.File.ReadAllLines("in.txt");
            string[] k = line[0].Split(' ');
            int licznik = 0;
            int n = int.Parse(k[0]); //ilość urządzeń sieciowych ( <= 1000 )
            int m = int.Parse(k[1]); //ilość wszystkich dostępnych połączeń między urządzeniami ( <= 1 000 000 )
            Krawedz[] krawedzie = new Krawedz[n - 1]; //tablica przechowująca gałęzie drzewa rozpinającego
            List<int> drzewo = new List<int>();
            int[,] macierz = new int[n + 1, n + 1]; //macierz wag, sąsiedztwa (0 oznacza, że nie jest sąsiadem)
            bool[] odwiedzone = new bool[n + 1]; //czy odwiedzono i-ty wierzchołek
            List<int>[] lista = new List<int>[n + 1]; //listy incydencji
            for (int i = 0; i <= n; i++)
            {
                lista[i] = new List<int>(); // tworzenie tablic
            }
            for (int i = 1; i <= n; i++)
            {
                odwiedzone[i] = false;
            }
            for (int i = 1; i <= m; i++)
            {
                k = line[i].Split(' ');
                lista[int.Parse(k[0])].Add(int.Parse(k[1]));
                lista[int.Parse(k[1])].Add(int.Parse(k[0]));
                macierz[int.Parse(k[0]), int.Parse(k[1])] = int.Parse(k[2]);
                macierz[int.Parse(k[1]), int.Parse(k[0])] = int.Parse(k[2]);
            }
            float suma = 0;
            int pom = 1;
            float p;
            int l = 0;
            int v = 1; //wierzchołek startowy
            odwiedzone[1] = true;
            for (int i = 0; i <= n - 2; i++)
            {
                foreach (int u in lista[v]) //dla kazdego sasiada wirzcholka v
                {
                    licznik++;
                    if (odwiedzone[u] == false) // jesli nie odwiedzilismy go
                    {
                        Krawedz wch = new Krawedz();
                        wch.u = u;
                        wch.v = v;
                        wch.priorytet = macierz[v, u];
                        kolejka.Dodaj(wch);         //dodajemy krawedz do kolejki priorytetowej
                    }
                }
                while (kolejka.Ilosc() != 0) //dopoki kolejka niepusta
                {
                    licznik++;
                    Krawedz w = new Krawedz();
                    w = kolejka.Korzen();
                    p = w.priorytet;
                    kolejka.Zdejmij();
                    if (odwiedzone[w.u] == false)
                    {
                        suma += p;
                        krawedzie[l] = w;
                        l++;
                        odwiedzone[w.u] = true;
                        pom = w.u;
                        break;
                    }

                }
                v = pom;
            }
            Console.WriteLine("Koszt: " + suma);
            StreamWriter sw = new StreamWriter("out.txt");
            sw.WriteLine(suma);
            Console.WriteLine("Krawedzie: ");
            foreach (Krawedz i in krawedzie)
            {
                Console.WriteLine(i.u + " - " + i.v + "  waga: " + i.priorytet);

            }

            //Wypisanie jakie wierzchołki zostały odwiedzone, potwierdzenie działania programu
            foreach (Krawedz i in krawedzie)
            {
                drzewo.Add(i.v);
                drzewo.Add(i.u);
            }
            drzewo.Sort();
            foreach(int i in drzewo)
            {
               Console.WriteLine(i);
             }

            //przegladanie grafu wszerz BFS
            //startowy wierzcholek = 1
            List<int> wynik = new List<int>();
            Queue<int> bfs = new Queue<int>();
            List<int>[] lista_bfs = new List<int>[n + 1]; //listy incydencji
            bool[] odwiedzone_bfs = new bool[n + 1]; //czy odwiedzono i-ty wierzchołek
            for (int i = 0; i <= n; i++)
            {
                lista_bfs[i] = new List<int>(); // tworzenie tablic
            }
            for (int i = 1; i <= n; i++)
            {
                odwiedzone_bfs[i] = false;
            }
            foreach (Krawedz i in krawedzie)
            {
                Console.WriteLine(i.v + " " + i.u);
                lista_bfs[i.v].Add(i.u);
                lista_bfs[i.u].Add(i.v);
            }
            odwiedzone_bfs[1] = true;
            bfs.Enqueue(1);
            int wierzcholek;
            while(bfs.Count != 0)
            {
                wierzcholek = bfs.First();
                wynik.Add(wierzcholek);
                bfs.Dequeue();
                foreach (int u in lista_bfs[wierzcholek]) //dla kazdego sasiada wirzcholka wierzcholek
                {
                    if (odwiedzone_bfs[u] == false) // jesli nie odwiedzilismy go
                    {
                        bfs.Enqueue(u);
                        odwiedzone_bfs[u] = true;
                    }
                }

            }
            Console.WriteLine("Wierzchołki zostałe odwiedzone w kolejności: ");
            foreach (int i in wynik)
            {
                Console.WriteLine(i);
            }

            //
            Console.WriteLine("Licznik: " + licznik);
            sw.Close();
            Console.ReadKey();
        }
    }
}