#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

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

const int Nmax=2e5+5;
const int Mmax=4e5+5;

int n, m;
int cost;
vector<pair<int, int>> sol;

struct edge{
    int a, b, c;
}e[Mmax];

bool cmp(edge x, edge y){
    return x.c<y.c;
}

struct DSU{
    int rep[Nmax];
    int sz[Nmax];

    DSU(int n){
        for (int i=1; i<=n; i++){
            rep[i]=i;
            sz[i]=1;
        }
    }

    int get_rep(int node){ // returneaza reprezentantul suprem pt node
        if (rep[node]==node)
            return node;
        return rep[node]=get_rep(rep[node]); // path compression
    }

    bool same_set(int a, int b){
        int ra=get_rep(a);
        int rb=get_rep(b);

        return ra==rb;
    }

    void join(int a, int b){
        int ra=get_rep(a);
        int rb=get_rep(b);

        if (ra==rb)
            return;

        if (sz[rb]>sz[ra])
            swap(ra, rb);

        rep[rb]=ra;
        sz[rb]+=sz[ra];
    }
};

void Kruskal(){
    DSU dsu(n);
    sort(e, e+m, cmp);

    for (int i=0; i<m; i++)
        if (!dsu.same_set(e[i].a, e[i].b)){
            dsu.join(e[i].a, e[i].b);
            cost+=e[i].c;
            sol.push_back({e[i].a, e[i].b});
        }
    
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for (auto it:sol)
        fout<<it.first<<' '<<it.second<<'\n';
}

int main(){

    fin>>n>>m;
    for (int i=0; i<m; i++){
        int a, b, c;
        fin>>a>>b>>c;

        e[i]={a, b, c};
    }

    Kruskal();

    return 0;
}