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

using namespace std;

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

const int NMAX = 400100;

int sol1[NMAX],sol2[NMAX],sol;
int n,m,p=1;
int disjoint[NMAX];

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

bool compare(edge a,edge b)
{
    return a.value<b.value;
}

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

void unite(int x,int y)
{
    disjoint[father(x)]=father(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,compare);

    for(int i=1;i<=n;i++)
    {
        disjoint[i]=i;
    }

    for(int i=1;i<=m;i++)
    {
        if(father(v[i].n1)!=father(v[i].n2))
        {
            sol+=v[i].value;
            sol1[p]=v[i].n1;
            sol2[p]=v[i].n2;
            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';
    }
}