//Se da un graf neorientat ponderat conex
//MST = submultime a muchiilor care conecteaza toate nodurile (fara cicluri) si suma ponderilor e minima

#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <queue>
#include <tuple> //get<0>(myTuple), get<1>(myTuple), get<2>(myTuple) îți permit să accesezi elementele tuple-ului.

using namespace std;

// Functor de comparare pentru `std::priority_queue` pentru a obține un min-heap
    struct Compare {
        bool operator()(tuple<int, int, int> a, tuple<int, int, int> b) {
            return get<2>(a) > get<2>(b); //comparatorului returnează true dacă primul element are prioritate mai mică (adică valoarea sa este mai mare) decât al doilea element
        }
    };

struct MST{
    int cost;
    vector<tuple<int,int,int>> edges;
};

class GrafPonderat
{
public:
    int N;
    vector<list<pair<int,int>>> listaAdiacenta;
    vector<bool> vizitat;
    //prioriry_queue<Tip, Container, Tipul Comparatorului>
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, Compare> pq; //min PQ dupa cost minim
    
    
    GrafPonderat(int N)
    {
        this->N = N;
        listaAdiacenta.resize(N + 1);
        vizitat.assign(N + 1, false);
    }

    // Adaugă o muchie între nodurile u și v
    void AdaugaMuchie(int u, int v, int cost) 
    {
        listaAdiacenta[u].push_back({v, cost}); // Adăugăm v în lista de adiacență a lui u
        listaAdiacenta[v].push_back({u, cost}); // Dacă graful este neorientat, adăugăm u în lista lui v
    }

    void AfisareListaAd()
    {
        for(int i=1; i<=N; i++)
            //if(!listaAdiacenta[i].empty()) //daca lista nodului i nu e vida, o afisez
            {
                cout<<i<<" : ";
                for(pair<int,int> nod : listaAdiacenta[i])
                    cout<<"("<<nod.first<<", "<<nod.second<<") ";
                cout<<endl;
            }
    }




    void addEdges(int nod)
    {
        vizitat[nod] = true;

        for(pair<int,int> vecin : listaAdiacenta[nod]) //iteram prin vecinii nodului si adaugam muchiile cu extremitatea nevizitata
        {
            if(!vizitat[vecin.first])
            {
                pq.push({nod, vecin.first, vecin.second});
            }
          

        }
    }

    MST Prim(int s)
    {
        int m = N-1; //nr de muchii in MST
        int edgeCount = 0; //contor pt nr de muchii din MST la un moment
        MST mst;
        mst.cost = 0; //cost total din MST
        mst.edges.resize(m, {0,0,0}); //{start, end, cost} muchiile incluse in MST

        addEdges(s); //adaugam muchiile adiacente primului nod in PQ

        while(!pq.empty() && edgeCount != m)
        {
            tuple<int,int,int> muchie = pq.top();
            pq.pop();
            int nod = get<1>(muchie); //nodul adiacent
            
            if(vizitat[nod])
                continue;

            mst.edges[edgeCount++] = muchie;
            mst.cost += get<2>(muchie); //adunam costul muchiei 

            addEdges(nod);
          
        }

        if(edgeCount != m)
        {
            cout<<"Graful nu are MST";
            mst.cost=0;
            mst.edges.resize(0);
            return mst;
        }

        return mst;    
    }

};

ifstream f("amp.in");
ofstream g("amp.out");
int main()
{
    int N,M,u,v,cost;
    f>>N>>M;
    GrafPonderat graf(N);
    
    for(int i=0; i<M; i++)
    {
        f>>u>>v>>cost;
        graf.AdaugaMuchie(u,v, cost);
    }

    
    MST mst = graf.Prim(1);
    if(mst.cost != 0 && mst.edges.size() != 0)
    {
        g<<mst.cost<<endl;
        g<<mst.edges.size()<<endl;
        int m = mst.edges.size();
        for(int i=0; i<m; i++)
            g<<get<0>(mst.edges[i])<<" "<<get<1>(mst.edges[i])<<endl;
    }

    return 0;
}