#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int N = 2e5 + 5;
vector <muchie> muchii;
int radacini[N];
vector <int> raspuns;

bool criteriu(muchie a, muchie b){
    return a.cost<b.cost;
}

int rad(int x){
    if(radacini[x]==x) return x;
    else return rad(radacini[x]);
}

int main()
{
    int n,m;
    ifstream in("apm.in");
    ofstream out("apm.out");
    in>>n>>m;
    for(int i=1;i<=n;i++)
        radacini[i] = i;
    int cost = 0;
    muchie w;
    while(m--){
        in>>w.x>>w.y>>w.cost;
        muchii.push_back(w);
    }
    sort(muchii.begin(),muchii.end(),criteriu);
    for(auto y: muchii){
        int p = rad(y.x);
        int u = rad(y.y);
        if(p != u){
            raspuns.push_back(y.x);
            raspuns.push_back(y.y);
            cost += y.cost;
            radacini[u] = radacini[p];
        }
    }
    out<<cost<<'\n';
    int l = raspuns.size();
    out<<l/2<<'\n';
    for(int i=0;i<l;i+=2){
        out<<raspuns[i]<<' '<<raspuns[i+1]<<'\n';
    }
    return 0;
}