#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define Nmax 200005

using namespace std;

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

struct muchie{
int x, y, c;
}v[Nmax];
int n, m, x, y, c;

int tt[Nmax];
long long sm;
vector <pair <int, int> > sol;

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

int root(int x)
{
    int r=x, y=0;
    while(tt[r]!=r) r=tt[r];

    while(tt[x]!=x)
    {
        y=tt[x];
        tt[x]=r;
        x=y;
    }

    return r;
}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        v[i]={x, y, c};
    }
    for (int i = 1; i <= n; i++)
        tt[i]=i;

    sort(v+1, v+m+1, cmp);

    //for (int i = 1; i <= m; i++)
    //    cout << v[i].x << " " << v[i].y << " " << v[i].c << '\n';

    for (int i = 1; i <= m; i++)
    {
        int x=root(v[i].x);
        int y=root(v[i].y);
        if(x!=y)
        {
            //cout << i << ' ';
            tt[x]=y;
            sm+=v[i].c;
            sol.push_back({v[i].x, v[i].y});
        }
    }
    //cout << '\n';
    g << sm << '\n';
    g << sol.size() << '\n';
    for (int i = 0; i < sol.size(); i++)
        g << sol[i].first << " " << sol[i].second << '\n';
    return 0;
}