#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("popcnt")

using namespace std;

ifstream fin  ("apm.in");
ofstream fout ("apm.out");

const int MAX_N = 200000;
const int MAX_M = 400000;
int n, m, sol;
queue<pair<int, int>> chosen;

int X, Y, C;
struct edge{
    int x, y, c;
    inline bool operator < (const edge &rhs) const{
        return c < rhs.c;
    }
} e[MAX_M + 5];

struct DSU{
    int parent[MAX_N + 5];
    int marime[MAX_N + 5];

    inline void build(){
        for(int nod=1; nod<=n; nod++){
            parent[nod] = nod;
            marime[nod] = 1;
        }
    }

    inline int get_root(int nod){
        if(parent[nod] == nod)
            return nod;
        else
            return parent[nod] = get_root(parent[nod]);
    }

    inline void join(int nod1, int nod2){
        int root1 = get_root(nod1);
        int root2 = get_root(nod2);
        if(root1 != root2){
            if(marime[root1] < marime[root2]){
                parent[root1] = root2;
                marime[root2] += marime[root1];
            }else{
                parent[root2] = root1;
                marime[root1] += marime[root2];
            }
        }
    }

    inline bool query_same_set(int nod1, int nod2){
        int root1 = get_root(nod1);
        int root2 = get_root(nod2);
        if(root1 == root2)
            return true;
        else
            return false;
    }
} tree;

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>e[i].x>>e[i].y>>e[i].c;
    sort(e+1, e+m+1);

    tree.build();
    for(int i=1; i<=m; i++){
        X = e[i].x, Y = e[i].y, C = e[i].c;
        if(tree.query_same_set(X, Y) == false){
            tree.join(X, Y);
            sol += C;
            chosen.push(make_pair(X, Y));
        }
    }

    fout<<sol<<"\n"<<n-1<<"\n";
    while(!chosen.empty()){
        fout<<chosen.front().first<<" "<<chosen.front().second<<"\n";
        chosen.pop();
    }
    return 0;
}
/**
**/