#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;
vector<int>v[N];

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

int rad(int x){
    while(radacini[x] != x){
        x = radacini[x];
    }
    return x;
}

void uupdate(int x,int val){
    radacini[x] = val;
    for(auto q:v[x]){
       if(radacini[q]!=val)
        uupdate(q,val);
    }
}

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] = 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;
}