#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int inf = 1e9;
vector<int> L[1000001];
int p[1000001];
int h[1000001];

struct Muchie {
    int x;
    int y;
    int c;
};

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

void unionn(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]++;
    }
}

int main() {
    int n, m, sol=0, nrmuchii=0;
    fin >> n >> m;

    for (int i = 1; i <= n; i++) {
        p[i] = i;
        h[i] = 0; 
    }

    vector<Muchie> edges; 
    vector<Muchie> partial; 

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

    std::sort(edges.begin(), edges.end(), [](const Muchie& a, const Muchie& b) {
        return a.c < b.c; 
    });

    for (const auto& edge : edges){
        if(find(edge.x)!=find(edge.y)){
            sol+=edge.c;
            unionn(edge.x,edge.y);
            partial.push_back({edge.x,edge.y,edge.c});
            nrmuchii++;  
            }
    }


    fout<<sol<<'\n'<<nrmuchii<<'\n';

    for (const auto& edge : partial){
        fout<<edge.y<<' '<<edge.x<<'\n';
    }

    return 0;
}