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

using namespace std;

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

struct apm{
int x, y, c;
}v[400005];

long long sm;
int n, m, x, y, c;
int tt[Nmax];
vector <pair <int, int> > sol;

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

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

    while(x!=tt[x])
    {
        int 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};
    }
    sort(v+1, v+m+1, cmp);
    for (int i = 1; i <= n; i++) tt[i]=i;

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

    return 0;
}