#include <cstdio>
#include <vector>
#include <algorithm>
#define vert 200001
using namespace std;

int n, m, x, y, z, i, father[vert], nr, cost, sol_x[vert], sol_y[vert];
vector < pair < int, pair <int, int> > > v;

int root(int x)
{
    if(father[x]!=x)
        father[x]=root(father[x]);
    return father[x];
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d", &x, &y, &z);
        v.push_back(make_pair(z, make_pair(x, y)));
    }
    for(i=1;i<=n;++i)
        father[i]=i;
    sort(v.begin(), v.end());
    i=0;
    while(i<v.size() && nr <= n-1)
    {
        z=v[i].first;
        x=v[i].second.first;
        y=v[i].second.second;
        if(root(x)!=root(y))
        {
            father[father[y]]=father[x];
            cost+=z;
            sol_x[++nr]=x; sol_y[nr]=y;
        }
        ++i;
    }
    printf("%d\n%d\n", cost, nr);
    for(i=1;i<=nr;++i)
        printf("%d %d\n", sol_x[i], sol_y[i]);
    return 0;
}