#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

#define nmax 200001
#define mmax 400001

int n,m,i,k;
int tata[nmax],mar[nmax],rez1[nmax],rez2[nmax],nod1,nod2,tata1,tata2,suma;

struct Edge
{
    int x,y,cost;
}muchii[nmax];
bool Compare(Edge a, Edge b)
{
    return a.cost < b.cost;
}

int t(int x)
{
    while(tata[x]!=x)
        x=tata[x];
    return x;
}

int main()
{
    f>>n>>m;

    for(i=1;i<=m;i++)
        f>>muchii[i].x>>muchii[i].y>>muchii[i].cost;

    sort(muchii+1, muchii+m+1, Compare);

    for(i=1;i<=n;i++)
    {
        tata[i]=i;
        mar[i]=1;
    }
    for(i=1;i<=m;i++)
    {
        nod1=muchii[i].x; nod2=muchii[i].y;

        tata1=t(nod1); tata2=t(nod2);
        if(tata1!=tata2)
        {
            if(mar[tata1]>mar[tata2])
            {
                tata[tata2]=tata1;
            }
            else if(mar[tata1]<mar[tata2])
            {
                tata[tata1]=tata2;
            }
            else
            {
                tata[tata1]=tata2;
                mar[tata2]+=1;
            }
            suma+=muchii[i].cost;
            k++;
            rez1[k]=nod1;
            rez2[k]=nod2;
        }
    }
    g<<suma<<'\n'<<n-1<<'\n';
    for(i=1;i<=k;i++)
        g<<rez1[i]<<" "<<rez2[i]<<'\n';

    return 0;
}