//Kruscal

#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int parinte[200001];
int sz[200001];

struct muchie {
    int x,y,cost;
};

vector<muchie>muchii;


int reprezentant(int a) {
    if (parinte[a]==a) return a;
    return parinte[a] = reprezentant(parinte[a]);
}

void unire(int a,int b) {

    if (a==b) return;
    else if (sz[a]<sz[b]) swap(a,b);

    parinte[b]=a;
    sz[a]+=sz[b];
}

bool arbore(int x,int y) {
    int a=reprezentant(x);
    int b=reprezentant(y);
    if (a==b) return false;

    unire(a,b);
    return true;
}

int main() {

    int n,m;
    fin>>n>>m;

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

    for (int i = 1; i <= n; i++) {
        parinte[i] = i;
        sz[i] = 1;
    }

    sort(muchii.begin(),muchii.end(), [](muchie &a, muchie &b) {
        return a.cost < b.cost;
    });

    int costtotal=0;
    vector<pair<int,int>> muchii_arbore;

    for (auto &m:muchii) {
        if (arbore(m.x,m.y)==true) {
            costtotal+=m.cost;
            muchii_arbore.push_back({m.x,m.y});
        }
    }

    fout << costtotal << "\n";
    fout << muchii_arbore.size() << "\n";
    for (auto &e : muchii_arbore)
        fout << e.first << " " << e.second << "\n";

}