#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;
#define MMAX 100100
#define NMAX 100100

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

pair <int, pair<int, int> > muchii[MMAX];
pair <int, int> MM[NMAX];

int n, m;
int grad[NMAX], tata[NMAX];


void CitireGraf(int m)
{
    int i, x, y, c;
    for(i = 1; i <= m; i++)
    {
        f>>x>>y>>c;
        muchii[i] = make_pair(c, make_pair(x, y));
    }
}

int FindFather(int nod)
{
    if(tata[nod] == nod)
        return nod;
    tata[nod] = FindFather(tata[nod]);
    return tata[nod];
}
void init(int n)
{
    int i;
    for(i = 1; i <=n; i++)
    {
        tata[i]=i;
        grad[i]=1;
    }
}
void combina(int x, int y)
{
    int fx, fy;
    fx = FindFather(x);
    fy = FindFather(y);

    if(fx != fy)
    {
        if(grad[fx] > grad[fy])
        {
            tata[fy] = fx;
            grad[fx] += grad[fy];
        }
        else
        {
            tata[fx] = fy;
            grad[fy] += grad[fx];
        }
    }
}
int main()
{
    int i, c=0, x, y, t=0;
    f >> n >> m;

    init(n);
    CitireGraf(m);

    sort(muchii+1, muchii + m+1);

    for(i = 1; i <= m; i++)
    {

        x = muchii[i].second.first;
        y = muchii[i].second.second;
        if(FindFather(x) != FindFather(y))
        {
            t++;
            MM[t] = make_pair(x, y);
            combina(x,y);
            c += muchii[i].first;
        }
    }
    g<<c<<"\n"<<t<<"\n";

    for(i = 1; i <=t; i++)
        g<<MM[i].first<<" "<<MM[i].second<<"\n";
    return 0;
}