#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back

ifstream fin("apm.in");
ofstream fout("apm.out");

typedef struct node///nu vad niciun motiv pragmatic pentru care sa folosesti rank ul ala deci plm
{
	int data;
	struct node* parent;
    node(int x)
    {
        data = x;
        parent = nullptr;
    }
};

typedef struct graf
{
	int V,E;
	unordered_map <int, node*> nodes; ///ba deci plm peste tot lucrezi cu indici ca asa iti da problema idk
                                      ///si gen voiam sa tin pentru nodul x, node ul corespunzator din padurea aia
                                      ///si gen daca aveam vector n aveam apelare in O(1) asa ca am bagat hash ul asta
                                      ///Puteai sa tii vector dar dupa trebuia sa incropesti functiile alea pe care ti le da
                                      ///si nu se mai pastra practic invariantul structurii tale de date (adica trebuia sa fii atent
                                      ///sa dai make set in ordine de la 1 la n, si era cam laba
    vector <pair<int, pair<int, int> > > edges;
};

graf g;
vector <pair<int,int> > ans; ///muchiile selectate pentru apm
int sum; ///suma finala

void make_set(int x)
{
    node *q = new node(x);
    g.nodes[x]=q;
}

///in find_set tre sa faci optimizarea aia de scurtare a arborelui
///gen daca ai
/*
1 -> 2 -> 3 -> 4
si apelezi find_set(4)
dupa ar trebui sa arate cam asa
1 -> 2
  -> 3
  -> 4
  (gen tot ce e sub bagi direct la radacina)
*/
int find_set(int x)
{
    node* ancestor = g.nodes[x];
    while(ancestor->parent!=nullptr)
        ancestor = ancestor->parent;
    node* it = g.nodes[x];
    while(it->parent!=nullptr)
    {
        node* q = it->parent;
        it->parent = ancestor;
        it = q;
    }
    return ancestor->data;
}

void union_(int a, int b)
{
    node* x = g.nodes[a];
    node* y = g.nodes[b];
    while(x->parent!=nullptr)
        x = x->parent;
    while(y->parent!=nullptr)
        y = y->parent;
    ///unesc radacinile
    x->parent = y;
}

int main()
{
    fin.sync_with_stdio(false);
    fout.sync_with_stdio(false);


    fin>>g.V>>g.E;

    ///creare multime noua pentru fiecare nod
    for(int i=1; i<=g.V; ++i)
    {
        make_set(i);
    }

    ///citire muchii
    for(int i=0; i<g.E; ++i)
    {
        int a, b, cost;
        fin>>a>>b>>cost;
        g.edges.pb(mp(cost,mp(a,b)));
    }

    sort(g.edges.begin(), g.edges.end());

    for(auto it:g.edges)
    {
        int a = it.s.f;
        int b = it.s.s;
        int cst = it.f;
        if(find_set(a)!=find_set(b))
        {
            union_(a,b);
            sum+=cst;
            ans.pb(mp(a,b));
        }
    }

    fout<<sum<<'\n';
    fout<<ans.size()<<'\n';
    for(auto it:ans)
    {
        fout<<it.f<<' ' <<it.s<<'\n';
    }
}