#include <iostream>
#include<algorithm>
#include<stdio.h>
#include<bitset>
using namespace std;
int w[200001],i,j,k,m,n,p,nr,x,y,c,X,Y,q;
bitset<400001>B;
struct muchie
{
    int x,y,c;
}v[400001];
struct muchie1{int x,y;}v1[400001];
int mx(int a,int b)
{
    if(a>b)return a;
    return b;
}
int mn(int a,int b)
{
    if(a<b)return a;
    return b;
}
bool compare(muchie a,muchie b)
{
    if(a.c==b.c)return(a.x<b.x);
    return (a.c<b.c);
}
int main()
{
    FILE*f=fopen("apm.in","r");
    fscanf(f,"%d%d",&n,&m);for(i=1;i<=n;++i)w[i]=i;
    for(p=0;p<m;++p)
    {
        fscanf(f,"%d%d%d",&x,&y,&c);
        v[p].x=mn(x,y);
        v[p].y=mx(x,y);
        v[p].c=c;
    }
    fclose(f);
    sort(v,v+m,compare);nr=0;c=0;
    for(j=0;nr<n-1;++j)
    {
        x=v[j].x;y=v[j].y;
        if(w[x]!=w[y])
        {
            p=mn(w[y],w[x]);
            q=mx(w[y],w[x]);for(i=q;i<=n;++i)if(w[i]==q)w[i]=p;
            B[j]=1;
            //v1[nr].x=v[nr].x;v1[nr].y=v[nr].y;
            ++nr;c+=v[j].c;
            //cout<<x<<" "<<y<<'\n';
            //for(i=1;i<=n;++i)cout<<w[i]<<" ";
            //cout<<'\n';
        }
    }
    //cout<<c;
    FILE*g=fopen("apm.out","w");
    fprintf(g,"%d\n%d\n",c,nr);
    p=0;i=0;while(p<nr)
    {
        if(B[i]>0)
        {
            ++p;
            fprintf(g,"%d %d\n",v[i].x,v[i].y);
        }
        ++i;
    }
    fclose(g);
    return 0;
}