#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMAX=400100;

int sol1[NMAX];
int sol2[NMAX];
int sol;

int dj[NMAX];

int n,m;

struct edge
{
    int value,n1,n2;
}v[NMAX];

bool cmp(edge x,edge y)
{
    return y.value>x.value;
}

int mult(int x)
{
    if(dj[x]==x)
        return x;
    dj[x]=mult(dj[x]);
    return dj[x];
}

void unite(int x,int y)
{
    dj[mult(x)]=mult(y);
}

int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        in>>x>>y>>z;
        v[i].n1=x;
        v[i].n2=y;
        v[i].value=z;
    }
    sort(v+1,v+m+1,cmp);
    int p=1;

    for(int i=0;i<=n;i++)
    {
        dj[i]=i;
    }

    for(int i=1;i<=m;i++)
    {
        int x=v[i].n1;
        int y=v[i].n2;
        if(mult(x)!=mult(y))
        {
            sol1[p]=x;
            sol2[p]=y;
            sol+=v[i].value;
            unite(x,y);
            p++;
        }
    }
    p--;
    out<<sol<<'\n'<<p<<
    '\n';
    for(int i=1;i<=p;i++)
    {
        out<<sol1[i]<<" "<<sol2[i]<<'\n';
    }
}