#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <vector>
#include <bitset>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
#define MAXN 200005
struct nodh{
    int dela;
    int urm;
    int cost;
};
struct nod{
    int urm;
    int cost;
};

bool comp(nodh a, nodh b) {
    return a.cost>b.cost;
}

vector<nod> graf[MAXN];
vector<nodh> heap,rez;
bitset<MAXN> viz;
int i,j,n,m,cost,vizitate,a,b,c;
nod naux;
nodh haux,haux2;



int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++) {
        fin>>a>>b>>c;
        naux.cost=c;
        naux.urm=b;
        graf[a].push_back(naux);
        naux.urm=a;
        graf[b].push_back(naux);
    }
    haux.cost=0; haux.urm=1; haux.dela=0;
    heap.push_back(haux);

    while (!heap.empty()) {
        if (vizitate==n) break;
        haux=heap[0];
        pop_heap(heap.begin(),heap.end(),comp);
        heap.pop_back();
        if (!viz[haux.urm]) {
            rez.push_back(haux);
            viz[haux.urm]=1;
            vizitate++;
            cost+=haux.cost;
            if (vizitate==n) break;
            haux2.dela=haux.urm;
            for(i=0;i<graf[haux.urm].size();i++) {
                if (!viz[graf[haux.urm][i].urm]) {
                    haux2.urm=graf[haux.urm][i].urm;
                    haux2.cost=graf[haux.urm][i].cost;
                    heap.push_back(haux2);
                    push_heap(heap.begin(),heap.end(),comp);
                }
            }
        }
    }
    fout<<cost<<"\n";
    fout<<rez.size()-1<<"\n";
    for(i=1;i<rez.size();i++) {
        fout<<rez[i].dela<<" "<<rez[i].urm<<"\n";
    }

    fout.close();
    return 0;
}