#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int nmax=400005;

int N,M,sz[nmax/2],m[nmax/2],ct,sum,x1,x2,v1,v2;

struct muchie
{
    int cost,x,y;
}a[nmax],sol[nmax];

bool comp(muchie A , muchie B)
{
    return A.cost < B.cost || (A.cost==B.cost && A.x<B.x) || (A.cost==B.cost && A.x==B.x && A.y < B.y);
}

int Find(int x)
{
    int root=x,aux;

    while(m[root]!=root) root=m[root];

    while(m[x]!=root)
    {
        aux=m[x];
        m[x]=root;
        x=aux;
    }

    return root;
}

void Union(int A , int B)
{
    int root_A , root_B;

    root_A=Find(A);
    root_B=Find(B);

    if(sz[root_A] > sz[root_B])
    {
        sz[root_A]+=sz[root_B];
        m[root_B]=root_A;
    }
    else
    {
        sz[root_B]+=sz[root_A];
        m[root_A]=root_B;
    }
}


void read()
{
    fin>>N>>M;

    for(int i=1;i<=M;++i)
    {
        fin>>a[i].x>>a[i].y>>a[i].cost;
    }

    for(int i=1;i<=N;++i) {sz[i]=1; m[i]=i;}

    sort(a+1,a+M+1,comp);

    for(int i=1;i<=M && ct<N-1;++i)
    {
        x1=a[i].x;
        x2=a[i].y;

        v1=Find(x1);
        v2=Find(x2);

        if(v1!=v2)
        {
            Union(x1,x2);
            sum+=a[i].cost;
            ct++;
            sol[ct].x=x1;
            sol[ct].y=x2;
        }
    }

    fout<<sum<<"\n"<<ct<<"\n";

    for(int i=1;i<=ct;++i)
    {
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";
    }

}

int main()
{
    read();
    return 0;
}