#include <bits/stdc++.h>
#define LMAX 100001

using namespace std;

const int NMAX=4e5+5;
int p[NMAX],r[NMAX];
int Find(int u){
    return p[u]=(u==p[u]?u:Find(p[u]));
}
void Union(int u, int v){
    u=Find(u),v=Find(v);
    if(u==v) return;
    if(r[u]>r[v]) u^=v,v^=u,u^=v;
    p[u]=v;r[v]+=r[u];
}
struct edge{
    int u,v,cost;
}e[NMAX];
bool cmp(edge a, edge b){
    if(a.cost<b.cost) return true;
    if(a.cost>b.cost) return false;
    if(a.u<b.u) return true;
    if(a.u>b.u) return false;
    return a.v<b.v;
}
int main()
{
    FILE* fin=fopen("apm.in","r");
    FILE* fout=fopen("apm.out","w");
    int n,m;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=1;i<=n;i++) r[i]=1,p[i]=i;
    for(int i=0;i<m;i++)
        fscanf(fin,"%d%d%d",&e[i].u,&e[i].v,&e[i].cost);
    sort(e,e+m,cmp);
    int total=0;
    vector<int> ans;
    for(int i=0;i<m;i++){
        if(Find(e[i].u)!=Find(e[i].v)){
            ans.push_back(i),total+=e[i].cost;
            Union(e[i].u,e[i].v);
        }
    }
    fprintf(fout,"%d\n%d\n",total,int(ans.size()));
    for(int i=0;i<ans.size();i++)
        fprintf(fout,"%d %d\n",e[ans[i]].u,e[ans[i]].v);
    return 0;
}