#include<fstream>
#include<vector>
#include<queue>
#define N 200010
using namespace std;

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

struct lat {
    int a,b,c;
};

struct cmp {
    bool operator()(lat a, lat b) {
        return a.c>b.c;
    }
};

int n,m,nrdif,a[N],b[N],c[N],nrrr,nrr,nu;
vector<lat> v[N];
vector<pair<int,int> > rez;
priority_queue<lat,vector<lat>, cmp> h;
bool ver[N];

int main() {
    int i;
    lat aa;

    in >> n >> m;

    for(i=1;i<=m;++i) {
        in >> a[i] >> b[i] >> c[i];

        aa.a=a[i]; aa.b=b[i]; aa.c=c[i];

        v[a[i]].push_back(aa);

        aa.a=b[i]; aa.b=a[i];
        v[b[i]].push_back(aa);
    }

    vector<lat>::iterator it;

    for(it=v[1].begin();it!=v[1].end();++it)
        h.push(*it);

    ver[1]=true;

    while(!h.empty()) {

        nrrr=h.top().b;
        nrr=h.top().a;
        nu=h.top().c;
        h.pop();

        if(!ver[nrrr]) {
            for(it=v[nrrr].begin();it!=v[nrrr].end();++it)
                h.push(*it);

            ver[nrrr]=true;

            nrdif+=nu;

            rez.push_back(pair<int,int>(nrr,nrrr));
        }
    }

    out << nrdif << "\n" << n-1 << "\n";

    vector<pair<int,int> >::iterator ii;

    for(ii=rez.begin();ii!=rez.end();++ii)
        out << ii->first << " " << ii->second << "\n";

    return 0;
}