#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;
    }
};

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];
char buf[200005];int bp;
int n,m,cost;

void apm(int start) {
    viz[start] = true;
    for (it=v[start].begin();it!=v[start].end();it++)
        q.push(mkmuc(start,(*it).d,(*it).c));
    while (!q.empty()) {
        muchie nod = q.top(); q.pop();
        if (viz[nod.d]) continue;
        viz[nod.d] = true;
        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));
    }
}

char getch() {
    if (buf[bp] == 0 || bp >= 200000) {
        fread(buf,1,200000,stdin);
        bp = 0;
    }
    return buf[bp++];
}

char filter() {
    char ct = getch();
    while (ct != '-' && !('0' <= ct && ct <= '9')) ct = getch();
    return ct;
}

int cit() {
    int res=0,semn = 1;
    char ct = filter();
    if (ct == '-') semn = -1,ct=getch();
    while ('0' <= ct && ct <= '9') res = 10*res + ct-'0',ct=getch();
    return res*semn;
}

int main() {
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    n = cit(); m = cit();
    for (int i=1;i<=m;i++) {
        int a = cit(),b = cit(),c = cit();
        v[a].push_back(mkmuc(a,b,c));
        v[b].push_back(mkmuc(b,a,c));
    }
    apm(1);
    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;
}