#include <fstream>
#include<vector>
#include<algorithm>
#define pp pair<int,int>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pp> q;
struct edge{
    int x,y,c;
};
edge l[400005];
int n,m,t[200005],v[200005],cost;
void cit(){
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>l[i].x>>l[i].y>>l[i].c;
    fin.close();
}
bool cmp(edge a,edge b){
    return a.c<b.c;
}
int getRoot(int x){
    int r;
    r=x;
    while(r!=t[r])
        r=t[r];
    return r;
}
void unite(int x,int y){
    if(v[x]>v[y])
        t[y]=x;
    else
        t[x]=y;
    if(v[x]==v[y])
        v[y]++;
}
void apm(){
    int i,x,y,rootx,rooty;
    for(i=1;i<=m;i++){
        x=l[i].x;y=l[i].y;
        rootx=getRoot(x);
        rooty=getRoot(y);
        if(rootx!=rooty){
            unite(rootx,rooty);
            q.push_back(make_pair(l[i].x,l[i].y));
            cost+=l[i].c;
        }
    }
}
int main(){
    cit();
    for(int i=1;i<=n;i++){
        v[i]=i;
        t[i]=i;
    }
    sort(l+1,l+m+1,cmp);
    apm();
    fout<<cost<<'\n';
    fout<<q.size()<<'\n';
    for(vector<pp>::iterator it=q.begin();it!=q.end();it++)
        fout<<it->first<<" "<<it->second<<'\n';
    fout.close();
    return 0;
}