#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct muchie {
    int s,d,c;
};

struct comp {
    bool operator() (muchie &a,muchie &b) {
        return a.c > b.c;
    }
};

inline muchie mkmuc(int s,int d,int c) {
    muchie nou;
    nou.s = s;
    nou.d = d;
    nou.c = c;
    return nou;
}

priority_queue <muchie,vector<muchie>,comp> q;
vector <muchie> r;
vector <muchie> v[200005];
vector <muchie> :: iterator it;
bool viz[200005];
int n,m,cost;

int main() {
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        v[a].push_back(mkmuc(a,b,c));
        v[b].push_back(mkmuc(b,a,c));
    }
    int start = n/2,nr=0;
    viz[start] = true;
    for (it=v[start].begin();it!=v[start].end();it++)
        q.push(mkmuc(start,(*it).d,(*it).c));
    nr=1;
    while (nr<n) {
        muchie nod = q.top(); q.pop();
        if (viz[nod.d]) continue;
        viz[nod.d] = true;nr++;
        cost += nod.c;
        r.push_back(mkmuc(nod.s,nod.d,0));
        for (it=v[nod.d].begin();it!=v[nod.d].end();it++)
            q.push(mkmuc(nod.d,(*it).d,(*it).c));
    }
    printf("%d\n%d\n",cost,n-1);
    for (it=r.begin();it!=r.end();it++) {
        printf("%d %d\n",(*it).s,(*it).d);
    }
    return 0;
}