#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int x,y,c;
};
muchie a[400001];
int n,h[200001],tata[200001],r[200001],m,s,nr;
bool cmp(const muchie &a,const muchie &b)
{
    return a.c<b.c;
}
void uneste(int i,int j)
{
    if(h[i]>h[j])
    {
        tata[j]=i;
    }
    else
    {
        tata[i]=j;
        if(h[i]==h[j])
        {
            h[j]++;
        }
    }
}
int cauta(int x)
{
    if(tata[x]!=x)
    {
        tata[x]=cauta(tata[x]);
    }
    return tata[x];
}
int main()
{
    int i,j,k,cost;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        h[i]=1;
        tata[i]=i;
    }
    for(i=1;i<=m;i++)
    {
        f>>a[i].x>>a[i].y>>a[i].c;
    }
    sort(a+1,a+m+1,cmp);
    for(k=1;k<=m && nr<n-1;k++)
    {
        cost=a[k].c;
        i=cauta(a[k].x);
        j=cauta(a[k].y);
        if(i!=j)
        {
            uneste(i,j);
            s=s+cost;
            nr++;
            r[nr]=k;
        }
    }
    g<<s<<"\n";
    g<<nr<<"\n";
    for(i=1;i<=nr;i++)
    {
        g<<a[r[i]].x<<" "<<a[r[i]].y<<endl;
    }
    return 0;
}