#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie {
    int x, y, w;
    bool used;
};
bool comp (muchie a, muchie b) {
    return a.w < b.w;
}
vector <muchie> v;
vector <int> apm;
vector <int> rank;
int n, m, cost;

int Find(int x)
{
    if (apm[x] != x) {
        apm[x] = Find(apm[x]);
    }
    return apm[x];
}

void Union(int oldValue, int newValue)
{
    apm[oldValue] = apm[newValue];
    /*
    for (int j = 1; j <= n; j++) {
        if (apm[j] == oldValue) {
            apm[j] = newValue;
        }
    }
    */

}

int main()
{
    fin>>n>>m;
    muchie t;
    for (int i = 1; i <=m; i++) {
        fin>>t.x>>t.y>>t.w;
        t.used = false;
        v.push_back(t);
    }
    rank.resize(n + 1);
    apm.push_back(0);
    for (int i = 1; i <= n; i++) {
        apm.push_back(i);
    }

    sort(v.begin(), v.end(), comp);
    for (int i = 0; i < m; i++) {
        if (Find(v[i].x) != Find(v[i].y)) {
            cost = cost + v[i].w;
            v[i].used = true;
            if(rank[v[i].y] <= rank[v[i].x]) {
                Union(Find(v[i].y), Find(v[i].x));
                rank[v[i].y] += rank[v[i].x];
            } else {
                Union(Find(v[i].x), Find(v[i].y));
                rank[v[i].x] += rank[v[i].y];
            }
        }
    }

    fout<<cost<<'\n'<<n-1<<'\n';

    for (int i = 0; i < m; i++) {
        if (v[i].used == true) {
            fout<<v[i].y<<' '<<v[i].x<<'\n';
        }
    }

    return 0;
}
/*
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie {
    int x, y, w;
    bool used;
};
bool comp (muchie a, muchie b) {
    return a.w < b.w;
}
vector <muchie> v;
vector <int> apm;
int n, m, cost;

int Find(int x)
{
    return apm[x];
}

void Union(int oldValue, int newValue)
{
    for (int j = 1; j <= n; j++) {
        if (apm[j] == oldValue) {
            apm[j] = newValue;
        }
    }
}

int main()
{
    fin>>n>>m;
    muchie t;
    for (int i = 1; i <=m; i++) {
        fin>>t.x>>t.y>>t.w;
        t.used = false;
        v.push_back(t);
    }
    apm.push_back(0);
    for (int i = 1; i <= n; i++) {
        apm.push_back(i);
    }
    sort(v.begin(), v.end(), comp);
    for (int i = 0; i < m; i++) {
        if (Find(v[i].x) != Find(v[i].y)) {
            cost = cost + v[i].w;
            v[i].used = true;
            Union(Find(v[i].y), Find(v[i].x));
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for (int i = 0; i < m; i++) {
        if (v[i].used == true) {
            fout<<v[i].y<<' '<<v[i].x<<'\n';
        }
    }

    return 0;
}
*/