#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct muchie
{
    int n1,n2,cost;
};
struct rezultat
{
    int n1,n2;
};

rezultat rez[400001];
muchie m[400001];
int tata[200001];

bool cmp(muchie a, muchie b)
{
    if(a.cost<b.cost)
        return true;
    return false;
}

int root(int nod)
{
    if(tata[nod]==nod)
        return nod;
    return root(tata[nod]);
}

void unire(int x,int y)
{
    int rootx=root(x);
    int rooty=root(y);
    tata[rooty]=rootx;
}

int main()
{
    int n,nrm,sumcost=0;
    cin>>n>>nrm;
    for(int i=1;i<=n;i++)
        tata[i]=i;

    for(int i=1;i<=nrm;i++)
        cin>>m[i].n1>>m[i].n2>>m[i].cost;

    sort(m+1,m+nrm+1,cmp);

    int cnt=0;
    for(int i=1;i<=nrm and cnt<n-1; i++)
    {
        if(root(m[i].n1)!=root(m[i].n2))
        {
            cnt++;
            sumcost+=m[i].cost;
            rez[cnt].n1=m[i].n1;
            rez[cnt].n2=m[i].n2;
            unire(m[i].n1,m[i].n2);
        }
    }

    cout<<sumcost<<'\n'<<cnt<<'\n';
    for(int i=1;i<=cnt;i++)
        cout<<rez[i].n1<<" "<<rez[i].n2<<'\n';

    return 0;
}