#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> sol;
int N,M,rez,p[200100],nr[200100];


void compress(int x, int r) {
    int curr=x;
    while(curr!=r) {
        int temp = p[curr];
        p[curr] = r;
        curr = temp;
    }
}

int root(int x) {
    int ret=x;
    while(ret!=p[ret]) {
        ret = p[ret];
    }
    compress(x,ret);
    return ret;
}

void unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);

    if(nr[rx]<nr[ry]) {
        p[rx]=ry;
        nr[ry]+=nr[rx];
    } else {
        p[ry]=rx;
        nr[rx]+=nr[ry];
    }
}
bool connected(int x, int y) {
    if(root(x)==root(y)) {
        return true;
    }
    unite(x,y);
    return false;
}

struct edge {
    int x,y,c;
} m[400100];

int cmp (edge e1, edge e2) {
    return e1.c < e2.c;
}

int main () {
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;++i) {
        p[i]=i;
        nr[i]=1;
    }
    for(int i=1;i<=M;++i) {
        scanf("%d%d%d",&m[i].x,&m[i].y,&m[i].c);
    }
    sort(m+1,m+M+1,cmp);
    for(int i=1;i<=M;++i) {
        if(!connected(m[i].x,m[i].y)) {
            rez += m[i].c;
            sol.push_back(i);
        }
    }
    printf("%d\n%d\n",rez,N-1);
    for(int i=0;i<sol.size();++i) {
        printf("%d %d\n",m[i].x,m[i].y);
    }
    return 0;
}