#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct nod {int x,y,dist;} a[200000],sol[200000];
int sum,t[400000],r[400000];
long long int n,k,m;
bool cond(nod n1, nod n2)
{   return (n1.dist<n2.dist);
}
int Find(int x)
{   int rad;
    for(rad=x;rad!=t[rad];rad=t[rad]);
    while(x!=t[x])
    {   int c=t[x];
        t[x]=rad;
        x=c;
    }
    return rad;
}
void Unite(int x, int y)
{   if(r[x]<r[y]) t[x]=y;
    else t[y]=x;
    if(r[x]==r[y]) r[x]++;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)   t[i]=i;
    for(int i=1;i<=m;i++)   f>>a[i].x>>a[i].y>>a[i].dist;
    sort(a+1,a+m+1,cond);
    for(int i=1;i<=m;i++)
    {   if(Find(a[i].x)!=Find(a[i].y))
        {   Unite(Find(a[i].x),Find(a[i].y));
            sol[++k]=a[i];
            sum+=a[i].dist;
        }
    }
    g<<sum<<'\n';
    g<<k<<'\n';
    for(int i=1;i<=k;i++) g<<sol[i].x<<' '<<sol[i].y<<'\n';

    return 0;
}