#include <bits/stdc++.h>
using namespace std;

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

struct muchie{
    int  x, y, c;
    bool sel;
};
vector<muchie>v;
vector<int> t, h;

bool cmp(const muchie &A, const muchie &B){
    return A.c<B.c;
}

int Radacina(int x){
    while(x!=t[x])
        x=t[x];
    return x;
}

void Unificare(int x, int y){
    if(h[x]>h[y]){
        t[y]=x;
    }
    else if(h[y]>h[x])
        t[x]=y;

    else{
        h[x]++;
        t[y]=x;
    }
}

int main(){
    int n, m, cost=0, rx, ry;
    muchie temp;
    fin>>n>>m;
    temp={0, 0, 0, 0};
    t.assign(n+1, 0);
    h.assign(n+1, 1);
    v.push_back(temp);
    for(int i=1;i<=n;++i)
        t[i]=i;

    for(int i=1;i<=m;++i){
        fin>>temp.x>>temp.y>>temp.c;
        temp.sel=0;
        v.push_back(temp);
    }
    sort(v.begin()+1, v.end(), cmp);
    int cnt=0;
    for(int i=1;i<=m && cnt<n-1;++i){
        rx=Radacina(v[i].x);
        ry=Radacina(v[i].y);
        if(rx!=ry){
            Unificare(rx, ry);
            v[i].sel=1;
            cost+=v[i].c;
            cnt++;
        }
    }
    fout<<cost<<"\n";
    fout<<cnt<<"\n";
    for(int i=1;i<=m;++i)
        if(v[i].sel)
            fout<<v[i].x<<" "<<v[i].y<<"\n";

    fin.close();
    fout.close();
    return 0;
}