#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#define N 250005

using namespace std;

struct nod
{
    int x, y, c;
}nou;
int n, m, t[N], cost, nr;
vector <nod> g, sol;
vector <nod>::iterator it;

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d\n", &nou.x, &nou.y, &nou.c);
        g.push_back(nou);
        g.push_back(nou);
    }
}

int cmp(nod e, nod f)
{
    return (e.c<f.c);
}

int multime(int x, int y)
{
    int r1=t[x], r2=t[y];
    while(r1!=t[r1])
        r1=t[r1];
    while(r2!=t[r2])
        r2=t[r2];
    return (r1!=r2);
}

void unific(int x, int y)
{
    int r1=t[x], r2=t[y], nr1=0, nr2=0;
    while(r1!=t[r1])
        r1=t[r1], nr1++;
    while(r2!=t[r2])
        r2=t[r2], nr2++;
    if(nr1<nr2)
        t[r1]=r2;
    else
        t[r2]=r1;
}

void apm()
{
    sort(g.begin(), g.end(), cmp);
    for(int i=1;i<=n;i++)
        t[i]=i;

    for(it=g.begin();it!=g.end();it++)
        if(multime(it->x, it->y))
        {
            cost+=it->c;
            unific(it->x, it->y);
            sol.push_back(*it);
        }
}

void afisare()
{
    printf("%d\n%d\n", cost, sol.size());
    for(it=sol.begin();it!=sol.end();it++)
        printf("%d %d\n", it->x, it->y);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    citire();
    apm();
    afisare();
    return 0;
}