#include <fstream>
#include <vector>
#include <algorithm>
#define VAL 200005
#define MCH 400005

using namespace std;

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

struct muchie
{
    int a, b, c;
};

muchie v[MCH];

int N, M, i, j, p1, p2;
int poz[VAL], sum;
int K, x[MCH], y[MCH];
vector<int> c[VAL];
vector<int>::iterator it;

bool cmp(muchie x, muchie y)
{
    return x.c<y.c;
}

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
      fin >> v[i].a >> v[i].b >> v[i].c;
    sort(v+1, v+M+1, cmp);
    for (i=1; i<=N; i++)
    {
        c[i].push_back(i);
        poz[i]=i;
    }
    for (i=1; i<=M; i++)
    {
        if (poz[v[i].a]!=poz[v[i].b])
        {
            K++;
            sum+=v[i].c;
            p1=poz[v[i].a];
            p2=poz[v[i].b];
            x[K]=v[i].a;
            y[K]=v[i].b;
            for (it=c[p2].begin(); it!=c[p2].end(); it++)
            {
                poz[*it]=p1;
                c[p1].push_back(*it);
            }
            c[p2].clear();
            if (c[p1].size()==N)
              break;
        }
    }
    fout << sum << '\n' << K << '\n';
    for (i=1; i<=K; i++)
      fout << x[i] << " " << y[i] << '\n';
    fin.close();
    fout.close();
    return 0;
}