#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n, m, A[200002], c[200002];
long long cost_total;

struct muchie
{
    int x,y,cost;
} G[400001],x;

void initializare()
{
    ifstream f("apm.in");
    f >> n >> m;
    for(int i=1; i<=m; i++)
    {
        f >> G[i].x >> G[i].y >> G[i].cost;
    }
    for(int i=1; i<=n; i++)
        c[i]=i;
        f.close();
}

void sortare_muchii(int st, int dr)
{
    int i, j;
    if(st<dr)
    {
       x=G[st]; i=st; j=dr;
       while(i<j)
       {
        while(i<j && G[j].cost>=x.cost)
        j--;
       G[i]=G[j];
        while(i<j && G[i].cost<x.cost)
        i++;
        G[j]=G[i];
       }
       G[i]=x;
    sortare_muchii(st, i-1);
    sortare_muchii(i+1, dr);
    }
}

void afisare()
{
    ofstream g("apm.out");
    int i;
    g<<cost_total<<"\n";
    g<<n-1<<"\n";
    for(i=1; i<n; i++)
        g<<G[A[i]].x<<" "<<G[A[i]].y<<"\n";
    g.close();
}

int main()
{
    int i, j, minn, maxx, NrMSel=0;
    initializare();

     sortare_muchii(1,m);

    for(i=1; NrMSel<n-1; i++)
    {
        if(c[G[i].x]!=c[G[i].y])
        {
            A[++NrMSel]=i;
            cost_total=cost_total+G[A[NrMSel]].cost;
            if(c[G[i].x]<c[G[i].y])
            {
              minn=c[G[i].x];
              maxx=c[G[i].y];
            }
            else
            {
              minn=c[G[i].y];
              maxx=c[G[i].x];
            }
            for(j=1; j<=n; j++)
                if(c[j]==maxx) c[j]=minn;
        }
    }
    afisare();
    return 0;
}