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

#define MMAX 400005
#define NMAX 200005
using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct muchie{
    int x, y, c;
}a[MMAX], sol[MMAX];

bool cmp (muchie a, muchie b)
{
    if(a.c==b.c)
        return a.x<=b.x;
    return a.c<b.c;
}

int n, m, t[NMAX], cost, muchii;

int find_tata(int nod)
{
    int cnod=nod;
    while(t[nod]!=nod)
        nod=t[nod];
    t[cnod]=nod;
    return nod;
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1, a+m+1, cmp);
    for(int i=1; i<=n; i++)
        t[i]=i;
    for(int i=1; i<=m; i++)
    {
        int tx=find_tata(a[i].x);
        int ty=find_tata(a[i].y);
        if(tx!=ty)
        {
            cost+=a[i].c;
            muchii++;
            sol[muchii]=a[i];
            t[tx]=ty;
        }
    }
    fout<<cost<<"\n";
    fout<<muchii<<"\n";
    for(int i=1; i<=muchii; i++)
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";
    return 0;
}