//Kruscal

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

ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<int,int>> adj[200001];
int viz[200001];
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;
    int par = reprezentant(parinte[a]);
    return par;
}

int unire(int a,int b) {

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

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

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

    unire(x,y);
    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({x,y});
        }
    }

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

}