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

using namespace std;

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

const int NMAX = 200005;
int sol1[NMAX],sol2[NMAX],sol;
int disjoint[NMAX];
int n,m;

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

bool cmp(edges a,edges b)
{
    return a.value<b.value;
}

void citire()
{
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x1,x2,xvalue;
        in>>x1>>x2>>xvalue;
        v[i].n1 = x1;
        v[i].n2 = x2;
        v[i].value = xvalue;
    }
}

int getFather(int x)
{
    if(disjoint[x]==x)
    {
        return x;
    }
    else
    {
        disjoint[x]=getFather(disjoint[x]);
        return disjoint[x];
    }
}

void unite(int x,int y)
{
    disjoint[getFather(x)] = getFather(y);
}



int main()
{
    citire();
    sort(v+1,v+m+1,cmp);
    for(int i=1; i<=n; i++)
    {
        disjoint[i] = i;
    }
    int p=1;
    for(int i=1; i<=m; i++)
    {
        if(getFather(v[i].n1)!=getFather(v[i].n2))
        {
            sol1[p]=v[i].n1;
            sol2[p]=v[i].n2;
            sol+= v[i].value;
            unite(v[i].n1,v[i].n2);
            p++;
        }
    }
    out<<sol<<'\n'<<p-1<<'\n';
    for(int i=1; i<p; i++)
    {
        out<<sol1[i]<<" "<<sol2[i]<<'\n';
    }
}