#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

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

struct edge {
    int x,y,c;
};

bool cmp(edge a,edge b)
{
    return a.c < b.c;
}

const int N = 200010;
const int M = 400010;

int n,m,cst,gr[N];
edge a[M];
vector<int> ans;

int _gr(int x)
{
    if ( x == gr[x] ) return gr[x];
    gr[x] = _gr(gr[x]);
    return gr[x];
}

void unite(int x,int y)
{
    x = _gr(x);
    y = _gr(y);
    gr[x] = y;
}

int main()
{
    F>>n>>m;
    cst = 0;
    for (int i=1;i<=n;++i)
        gr[i] = i;
    for (int i=1;i<=m;++i)
        F>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+m+1,cmp);

    for (int i=1;i<=m;++i)
        if ( _gr(a[i].x) != _gr(a[i].y) )
        {
            unite(a[i].x,a[i].y);
            cst += a[i].c;
            ans.push_back(i);
        }
    G<<cst<<'\n';
    G<<n-1<<'\n';
    for (int i=0;i<(n-1);++i)
        G<<a[ans[i]].x<<' '<<a[ans[i]].y<<'\n';
}