#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define NMAX 400010

using namespace std;

struct muchie {
    int a,b;
    int cost;
    muchie() {};
    muchie(int a, int b, int cost) : a(a), b(b), cost(cost) {};
};

muchie G[NMAX];
int N,M;
int gr[NMAX/2];

int grupa(int i) {
    if(gr[i] == i) return i;
    return gr[i] = grupa(gr[i]);
}

int compare(muchie a, muchie b) {
    return a.cost < b.cost;
}

void grupa_union(int a, int b) {
    gr[grupa(a)] = grupa(b);
}

int main()
{
    int a,b,c;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    cin>>N>>M;
    for(int i=0; i < M;++i) {
        cin>>a>>b>>c;
        G[i] = muchie(a, b, c);
    }

    sort(G, G + M, compare);
    int sm = 0;
    vector<int> sol;

    for(int i=1;i<=N;i++)
        gr[i]= i;

    for(int i=0; i < M; i++) {
        if(grupa(G[i].a) != grupa(G[i].b)) {
            sm += G[i].cost;
            sol.push_back(i);
            grupa_union(G[i].a, G[i].b);
        }
    }

    cout<< sm <<"\n"<<sol.size()<<"\n";
    for(int i=0;i < sol.size(); ++i) {
        cout<<G[sol[i]].a<<" "<<G[sol[i]].b<<"\n";
    }
}