#include <iostream>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#include <set>
using namespace std;


vector < pair <int,int> > muchii[400002];
int n, m; int v[400002];
int cmm1, cmm2, cmmc=1000000; //cea mai mica muchie;
int ctotal;
vector <pair <int,int> > selectate;


void citire() {
    ifstream fin("apm.in");
    fin>>n>>m;
    for (int i=0; i<m; i++) {
        int t1, t2, c;
        fin>>t1>>t2>>c;
        t1--; t2--;
        muchii[t1].push_back(make_pair(t2, c));
        muchii[t2].push_back(make_pair(t1, c));
        if (c<cmmc) {
            cmm1=t1; cmm2=t2; cmmc=c;
        }
    }
}

struct sort_set_prim {
    bool operator() (vector <int> a, vector <int> b) const {
        return a[2]<b[2];
    }
};

void prim_heap () {
    multiset < vector <int>, sort_set_prim> heap;
    v[cmm1]=1;
    for (int i=0; i<muchii[cmm1].size(); i++) {
        vector <int> tmp;
        tmp.push_back(cmm1);
        tmp.push_back(muchii[cmm1][i].first);
        tmp.push_back(muchii[cmm1][i].second);
        heap.insert(tmp);
    }
    while (!heap.empty()) {
        std::multiset <vector <int>, sort_set_prim>::iterator t=heap.begin();
        vector <int> cur=*t;
        heap.erase(t);
        int viz=0, neviz=0;
        if (v[cur[0]]==1 && v[cur[1]]==0) {viz=cur[0]; neviz=cur[1]; }
        else if (v[cur[0]]==0 && v[cur[1]]==1) { viz=cur[1]; neviz=cur[0]; }
        if (viz+neviz!=0) {
            v[neviz]=1;
            ctotal+=cur[2];
            selectate.push_back(make_pair(viz, neviz));
            for (int i=0; i<muchii[neviz].size(); i++) {
                if (!v[muchii[neviz][i].first]) {
                    vector <int> tmp;
                    tmp.push_back(neviz);
                    tmp.push_back(muchii[neviz][i].first);
                    tmp.push_back(muchii[neviz][i].second);
                    heap.insert(tmp);
                }
            }
        }
    }
}


void afisare() {
    ofstream fout("apm.out");
    fout<<ctotal<<endl<<n-1<<endl;
    for (int i=0; i<selectate.size(); i++) {
            fout<<selectate[i].first+1<<" "<<selectate[i].second+1<<endl;
    }
}

int main()
{
    citire();
    prim_heap();
    afisare();
    return 0;
}