#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int N=2e5+1;
int n,m,t[N],nr[N];
bool vf[N];
vector <pair<int,int>> sol;

struct ura{
    int x,y,c;
}a[N];

bool cmp(ura a, ura b){
    return a.c<b.c;
}

int radacina(int x){
    if(t[x]==0)
        return x;
    t[x]=radacina(t[x]);
    return t[x];
}

void join(int x, int y){
    int tx=radacina(x);
    int ty=radacina(y);
    if(nr[tx]>=nr[ty]){
        t[ty]=tx;
        nr[tx]+=nr[ty];
    }else{
        t[tx]=ty;
        nr[ty]+=nr[tx];
    }
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++){
        f>>a[i].x>>a[i].y>>a[i].c;
    }
    sort(a+1,a+m+1,cmp);
    int cost=0,nrm=0,i=1;
    while(i<=m && nrm<n-1){
        if(radacina(a[i].x)!=radacina(a[i].y)){
            vf[i]=true;
            cost+=a[i].c;
            join(a[i].x,a[i].y);
            sol.push_back({a[i].x,a[i].y});
            nrm++;
        }
        i++;
    }
    g<<cost<<'\n'<<sol.size()<<'\n';
    for(auto j:sol)
        g<<j.first<<" "<<j.second<<'\n';
    return 0;
}