#include <bits/stdc++.h>

using namespace std;

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

struct Dsu{

    vector<int> par;
    vector<int> siz;

    Dsu(int n){
        par.resize(n+1);
        siz.resize(n+1);
        for(int i=1;i<=n;i++)
        {
            par[i]=i;
            siz[i]=1;
        }
    }

    int get_par(int x){
        if(par[x]==x) return x;
        return par[x]=get_par(par[x]);
    }

    bool same_par(int a, int b){
        return get_par(a) == get_par(b);
    }

    bool join(int a, int b){
        a=get_par(a);
        b=get_par(b);
        if(a==b) return 0;

        if(siz[a]<siz[b]) swap(a,b);

        par[b]=a;
        siz[a]+=siz[b];

        return 1;
    }

};

struct muc{
    int a,b,c;

    bool operator <(muc other){
        return c<other.c;
    }
};

int main()
{
    int n,m;
    f>>n>>m;
    Dsu dsu = Dsu(n);
    vector<muc> v;
    vector<muc> arb;
    int tot=0;


    v.resize(m);
    for(int i=0;i<m;i++)
    {
        f>>v[i].a>>v[i].b>>v[i].c;
    }


    sort(v.begin(), v.end());

    for(auto e:v){
        if(dsu.join(e.a, e.b)){
            tot+=e.c;
            arb.push_back(e);
        }
    }


    g<<tot<<'\n'<<arb.size()<<'\n';

    for(auto e:arb)
    {
        g<<e.a<<' '<<e.b<<'\n';
    }

    return 0;
}