#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct mu {
    int x,y,cost;
} v[400100];
vector<pair<int,int>>sol;
int n,m,nr,T[200100],total;

bool comp(const mu &a,const mu &b) {
    return a.cost<b.cost;
}

void Union(int cx,int cy) {
    T[cy]=cx;
}

int Find(int i) {
    if(T[i]==0) {
        return i;
    }
    return T[i]=Find(T[i]);
}

int main() {
    f>>n>>m;
    for(int i=1; i<=m; i++) {
        f>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1,v+m+1,comp);
    for(int i=1; i<=m; i++) {
        int cx=Find(v[i].x);
        int cy=Find(v[i].y);
        if(cx!=cy) {
            Union(cx,cy);
            total+=v[i].cost;
            nr++;
            sol.push_back({v[i].x,v[i].y});
            if(nr==n-1) {
                break;
            }
        }
    }
    g<<total<<'\n'<<nr<<'\n';
    for(const auto &q:sol) {
        g<<q.first<<' '<<q.second<<'\n';
    }
    f.close();
    g.close();
    return 0;
}