#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

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

int super[200005];

struct muchie {int x;
               int y;
               int cost;} G[400005];
struct arbore {int x;
               int y;} A[400005];

void quicksort(int ls, int ld)
{
    int i=ls,j=ld, pivot=G[rand()%(j-i+1)+i].cost;
    muchie aux;
    if(i<=j)
    {
        while(G[i].cost<pivot)
            i++;
        while(G[j].cost>pivot)
            j--;
        if(i<=j)
        {
            aux=G[i];
            G[i]=G[j];
            G[j]=aux;
            i++;
            j--;
        }
    }
    if(ls<j)
        quicksort(ls,j);
    if(i<ld)
        quicksort(i,ld);
}

int find(int x)
{
    if(x==super[x])
        return x;
    else
    {
        super[x]=find(super[x]);
        return super[x];
    }
}
int main()
{
    int n,m,i,CT=0,k=0,sx,sy;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>G[i].x>>G[i].y>>G[i].cost;
    quicksort(1,m);
    for(i=1;i<=n;i++)
        super[i]=i;
    i=1;
    while(i<=m)
    {
        sx=find(G[i].x);
        sy=find(G[i].y);
        if(sx!=sy)
        {
            CT+=G[i].cost;
            super[sy]=sx;
            A[++k].x=G[i].x;
            A[k].y=G[i].y;
        }
        i++;
    }
    g<<CT<<'\n'<<k<<'\n';
    for(i=1;i<=k;i++)
        g<<A[i].x<<' '<<A[i].y<<'\n';
    return 0;
}