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

using namespace std;

int sef[200005];

int sef_suprem(int nod)
{
    if(sef[nod]==nod)
    {
        return nod;
    }
    return sef[nod]=sef_suprem(sef[nod]);
}

struct mch
{
    int x;
    int y;
    int c;
    bool operator<(const mch& alt) const
    {
        return c<alt.c;
    }
};
struct r
{
    int x;
    int y;
};

mch v[400005];
r rez[400005];

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

    int n,m;
    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1);
    for(int i=1;i<=n;i++)
    {
        sef[i]=i;
    }
    int s=0;
    int k=0;
    for(int i=1;i<=m;i++)
    {
        int sefx=sef_suprem(v[i].x);
        int sefy=sef_suprem(v[i].y);
        if(sefx!=sefy)
        {
            sef[sefx]=sefy;
            s+=v[i].c;
            k++;
            rez[k].x=v[i].x;
            rez[k].y=v[i].y;
        }
    }
    fout<<s<<'\n'<<k<<'\n';
    for(int i=1;i<=k;i++)
    {
        fout<<rez[i].x<<" "<<rez[i].y<<'\n';
    }


    fin.close();
    fout.close();
    return 0;
}