#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <algorithm>

#define IN "apm.in"
#define OUT "apm.out"

#define NMAX 200005
#define MMAX 400005

using namespace std;

struct Muchie
{
    int x, y, cost;
}G[MMAX];

int tata[NMAX], selectate, n, m, h[NMAX], A[NMAX], cost;

int caut(int x)
{
    int r=x, aux;
    while(tata[r])
        r=tata[r];
    while(tata[x])
    {
        aux=tata[x];
        tata[x]=r;
        x=aux;
    }
    return r;
}
void unire(int x, int y)
{
    if(h[x]>h[y])
        tata[y]=x;
    else
    {
        tata[x]=y;
        if(h[x]==h[y])
            h[y]++;
    }
}
void kruskal();
void citire();
int cmp(Muchie A, Muchie B)
{
    return A.cost < B.cost;
}
void afisare()
{
    int i;
    ofstream fout(OUT);
    fout<<cost<<'\n'<<selectate<<'\n';
    for(i=0;i<selectate;++i)
    {
        fout<<G[A[i]].x<<' '<<G[A[i]].y<<'\n';
    }
}

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}

void citire()
{
    int i;
    FILE * fin = freopen(IN, "r", stdin);
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d", &G[i].x, &G[i].y, &G[i].cost);
    }
}

void kruskal()
{
    int i, c1, c2;
    sort(G+1, G+m+1, cmp);
    for(i=1;selectate<n-1;++i)
    {
       c1=caut(G[i].x);
       c2=caut(G[i].y);
       if(c1!=c2)
       {
           unire(c1, c2);
           A[selectate++]=i;
           cost+=G[i].cost;
       }
    }
}