#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

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

const int N = 200001;
const int M = 400001;
int n, m, parent[N], nrc[N], sol[N][2], k;
int ct;

struct muchie {
    int x,y,c;
}v[M];

bool comp (muchie a, muchie b) {
    return a.c < b.c;
}

int fnd (int x)
{
    if (parent[x]==0) return x;
    parent[x]=fnd (parent[x]);
    return parent[x];
}
void unionn (int x, int y)
{
    int xx=fnd (x);
    int yy=fnd (y);
    if (xx==yy) return;
    if (nrc[xx]>nrc[yy])
    {
        parent[yy]=xx;
        nrc[xx]+=nrc[yy];
    }
    else
    {
        parent[xx]=yy;
        nrc[yy]+=nrc[xx];
    }
}

int main()
{
    in>>n>>m;
    for (int i = 1; i <= m; i++) {
        in>>v[i].x>>v[i].y>>v[i].c;
    }
    /*for (int i=1;i<=m;i++) {
        cout<<v[i].x<<' '<<v[i].y<<' '<<v[i].c<<'\n';
    }*/
    sort (v+1, v+m+1, comp);
    for  (int j=1;j<=n;j++)
    {
        parent[j] = 0;
    }

    for (int j = 1; j <= m; j++)
    {
        int xx = fnd (v[j].x);
        int yy = fnd (v[j].y);
        if (xx != yy)
        {
            unionn (v[j].x,v[j].y);
            ct+=v[j].c;
            sol[++k][0] = v[j].x;
            sol[k][1] = v[j].y;
        }
    }

    out<<ct<<'\n';
    out<<k<<'\n';
    for (int i = 1; i <= k; i++) {
        out<<sol[i][0]<<' '<<sol[i][1]<<'\n';
    }

    return 0;
}