#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
struct Edge {
    int u,v,w;
};

bool cmp(const Edge&a, const Edge&b){
    return a.w < b.w;
}

struct DSU {
    vector <int> parent, rank;

    DSU(int n){
        parent.resize(n+1);
        rank.resize(n+1,0);
        for(int i=1;i<=n;i++)
            parent[i]=i;
    }

    int find(int x){
        if(parent[x]!=x){
            parent[x] = find(parent[x]);
        }
        return parent[x]; 
    }

    bool unite(int u,int v){
        int ru = find(u);
        int rv = find(v);
        if(ru==rv)
            return false;
        if(rank[ru]<rank[rv])
            swap(ru,rv);
        if(rank[ru] == rank[rv]){
            rank[ru]++;
        }
        parent[rv] = ru;
        return true;
    }
};


using namespace std;
int main(){
    ifstream f("apm.in");
    ofstream g("apm.out");
    int m,n;
    f >> n >>m;
    vector<Edge> edges(m+1);
    for(int i=1;i<=m;i++){
        f>>edges[i].u>>edges[i].v>>edges[i].w;
    }

    sort(edges.begin(),edges.end(),cmp);

    DSU dsu(n);
    vector<Edge> mst;
    int total=0;

    for(const auto &e : edges){
        if(dsu.unite(e.u,e.v)){
            mst.push_back(e);
            total +=e.w;
        }
    }
    
    g << total << "\n";
    g << mst.size() << "\n";
    for (const auto &e : mst) {
        g << e.v  << " " << e.u <<"\n";
    }

    
    return 0;
}