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


int p[100001];
int h[100001];

int Find(int x){
    while (x!=p[x]){
        x=p[x];
    }

    return x;
}

void Union(int x, int y){
    x=Find(x);
    y=Find(y);

    if(h[x]<h[y]){
        p[x]=y;
    }
    else{
        if(h[x]>h[y]){
            p[y]=x;
        }
        else{
            p[x]=y;
            h[y]++;
        }
    }
}

bool comparePairs(const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) {
return a.second < b.second;
}


vector <pair<pair<int,int>,int>> muchii;

vector <pair<int,int>> solutie;

int main(){

    ifstream cin("apm.in");
    ofstream cout("apm.out");

    int n;
    cin>>n;
    int m;
    cin>>m;

    // Initialize Union-Find for all nodes
    for(int i=1; i<=n; i++){
        p[i]=i;
        h[i]=0;
    }

    for(int i=0; i<m; i++){
        int x,y,c;
        cin>>x>>y>>c;
        muchii.push_back(make_pair(make_pair(x,y),c));
    }

    sort(muchii.begin(), muchii.end(), comparePairs);

    int sol=0;

    for(const auto& e : muchii){
        if (Find(e.first.first) != Find(e.first.second)) {
            sol+=e.second;
            solutie.push_back(e.first);
            Union(e.first.first, e.first.second);
        }
    }

    cout<<sol<<'\n';
    cout<<solutie.size()<<'\n';
    for(const auto& i : solutie){
        cout<<i.first<<" "<<i.second<<'\n';
    }


    return 0;
}