#include<bits/stdc++.h>
#define N 200010

using namespace std;

struct lol {
    int x,y,c;
} M[2*N];

int n,m,k, s,p[N];

int find(int x) {
    return (x==p[x]?x:p[x]=find(p[x]));
}

bool cmp(lol l, lol r) {
    return l.c<r.c;
}

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin>>n>>m;
    for (int i=1; i<=m; i++) {
        int x,y,c;
        cin>>x>>y>>c;
        M[i]={x,y,c};
    }
    for (int i=1; i<=n; i++) p[i]=i;
    sort(M+1,M+1+m,cmp);
    for (int i=1; k!=n-1; i++) {
        int x=M[i].x, y=M[i].y, c=M[i].c;
        int a=find(x), b=find(y);
        if (a!=b) {
            p[a]=b;
            M[++k] = M[i];
            s+=c;
        }
    }
    cout<<s<<"\n"<<k<<'\n';
    for (int i=1; i<=n; i++) {
        cout<<M[i].x<<" "<<M[i].y<<'\n';
    }

    return 0;
}