/*
#include <bits/stdc++.h>
#include<fstream>
#include<vector>

using namespace std;

ifstream f("apm.in");
ofstream of("apm.out");


struct muchie
{
    int x,y,c;


}v[500000];


bool cmp(muchie a,  muchie b)
    {return a.c<b.c;}


int X[500000],Y[500000];


struct DSU{
    int rp[500000], sz[500000];



    DSU(int n)
    {
        for(int i=1;i<=n;i++)
        {
            rp[i]=i;
            sz[i]=1;
        }
    }

    int rep(int a)
    {
        if(a==rp[a])
        return a;
        else
        {return rp[a]=rep(rp[a]);}
    }





    bool frati(int a,int b)
    {
        if(rep(a)==rep(b))
            return 1;
        else return 0;
    }

    void unire(int a,int b)
    {
        int ra=rep(a);
        int rb=rep(b);



        if(sz[ra]<sz[rb])
        {
        rp[ra]=rp[rb];
        sz[rb]+=sz[ra];
        }
        else
        {
        rp[rb]=rp[ra];
        sz[ra]+=sz[rb];
        }


    }






};







int main()
{

    int n,m;
    int k=1,s=0;
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;

     sort (v, v+m, cmp);

    DSU dsu(n);

    for(int i=1;i<=m;i++)
    {
        if(!dsu.frati(v[i].x,v[i].y))
        {
            dsu.unire(v[i].x,v[i].y);
            k++;
            s+=v[i].c;
            X[k]=v[i].x;
            Y[k]=v[i].y;

        }
    }

    of<<s<<' '<<k;


    for(int i=1;i<k;i++)
       of<<X[k]<<' '<<Y[k];

    return 0;
}*/

#include <iostream>
#include <algorithm>
#include <fstream>

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

const int Mmax=4e5, Nmax=2e5+1;

int n, m, total, nrm;

int X[Mmax], Y[Mmax];

struct muchie{
    int x, y, c;
}v[Mmax];

bool cmp(muchie a,  muchie b){
    return a.c<b.c;
}


struct DSU{
    int rep[Nmax], sz[Nmax];

    /// constructor pentru DSU
    DSU(int n){
        for (int i=1; i<=n; i++){
            rep[i]=i;
            sz[i]=1;
        }
    }

    /// functie care ne da radacina arborelui nodului "nod"
    int get_rep(int nod){
        /// cu path compression
        if (nod==rep[nod])
            return nod;
        else{
            // cod lungut
            /*
            int rnod=get_rep(rep[nod]);
            rep[nod]=rnod;
            return rnod;
            */
            return rep[nod]=get_rep(rep[nod]);
        }
    }

    /// functie prin care verificam daca nodurile "a" si "b" sunt in aceasi componenta
    bool same_comp(int a, int b){
        int ra=get_rep(a);
        int rb=get_rep(b);

        if (ra==rb)
            return 1;
        else return 0;
    }

    /// functie care combina multimile nodurilor "a" si "b"
    void join (int a, int b){
        int ra=get_rep(a);
        int rb=get_rep(b);

        /// cu small to large

        /// bagam pe b in a
        if (sz[ra]>sz[rb]){
            rep[rb]=ra;
            sz[ra]+=sz[rb];
        }
        /// bagam pe a in b
        else{
            rep[ra]=rb;
            sz[rb]+=sz[ra];
        }
    }
};

int main()
{
    fin>>n>>m;

    DSU dsu(n);

    for (int i=0; i<m; i++)
        fin>>v[i].x>>v[i].y>>v[i].c;

    sort (v, v+m, cmp);

    for (int i=0; i<m; i++){
        if (!dsu.same_comp(v[i].x, v[i].y)){
            total+=v[i].c;
            dsu.join(v[i].x, v[i].y);

            X[nrm]=v[i].x;
            Y[nrm]=v[i].y;
            nrm++;
        }
    }

    fout<<total<<'\n';
    fout<<nrm<<'\n';
    for (int i=0; i<nrm; i++)
        fout<<X[i]<<' '<<Y[i]<<'\n';

    return 0;
}