#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define NMAX 200010

ifstream f("apm.in");
ofstream g("apm.out");

struct Edge{
    int first,second,cost;
};

vector<Edge>Solution;
int N,M,TT[NMAX],TotalCost;
Edge Edges[NMAX];

void Init(){
    for (int i = 1; i <= N; i++) {
        TT[i] = i;
    }
}

int Search(int x){
    if (TT[x] == 0)
        return x;
    
    TT[x] = Search(TT[x]);
    return TT[x];
}

bool Merge(int x, int y){
    x = Search(x);y = Search(y);
    if (x == y)
        return false;
    
    TT[y] = x;
    return true;
}

bool cmp(Edge i, Edge j){
    return i.cost < j.cost;
}

void Read(){
    f>>N>>M;
    for (int i = 1; i <= M; i++) {
        f>>Edges[i].first>>Edges[i].second>>Edges[i].cost;
    }
}


void Solve(){
    sort(Edges+1, Edges+M+1, cmp);
    for (int i = 1; i <= M; i++) {
        if (Merge(Edges[i].first, Edges[i].second)) {
            Solution.push_back(Edges[i]);
            TotalCost += Edges[i].cost;
        }
    }
}

void Write(){
     g<<TotalCost<<"\n"<<Solution.size()<<"\n";
    for (; !Solution.empty(); Solution.pop_back()) {
        g<<Solution.back().first<<" "<<Solution.back().second<<"\n";
    }
    
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}