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

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

const int NMAX = 2e5+5;

int n;

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

bool comp(edge x, edge y)
{
    return x.c < y.c;
}

vector<edge> v;
int tt[NMAX], rnk[NMAX];

int root(int x)
{
    int R;
    for(R=x; R!=tt[R]; R=tt[R]);

    int y;
    while(x != R)
    {
        y = tt[x];
        tt[x] = R;
        x = y;
    }
    return R;
}

void unite(int x, int y)
{
    if(rnk[x] > rnk[y])
    {
        tt[y] = x;
    }
    else
    {
        tt[x] = y;
    }
    if(rnk[x] == rnk[y])
    {
        rnk[y]++;
    }
}

vector<pair<int, int> > sol;

int kruskal()
{
    sort(v.begin(), v.end(), comp);

    int nr=0, cmin = 0, i = 0;
    while(nr < n - 1)
    {
        int n1 = v[i].x, n2 = v[i].y, c = v[i].c;
        int rx = root(n1), ry = root(n2);
        if(rx != ry)
        {
            unite(rx, ry);
            cmin += c;
            nr++;
            sol.push_back({n1, n2});
        }
        i++;
    }

    return cmin;
}

int main()
{
    int m, i, x, y, c;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        v.push_back({x, y, c});
    }

    for(i=1; i<=n; i++)
    {
        tt[i] = i;
        rnk[i] = 1;
    }

    cout<<kruskal()<<'\n';
    cout<<sol.size()<<'\n';
    for(auto el : sol)
    {
        cout<<el.first<<' '<<el.second<<'\n';
    }

    fin.close();
    fout.close();
    return 0;

}