#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
struct muchie
{
    int x,y;
    float c;
};
muchie a[400001];
int t[200001],h[200001],r[200001];
int Find(int x)
{
    while(t[x]!=0)
        x=t[x];
    return x;
}

void Union(int x,int y)
{
    if(h[x]>h[y])
        t[y]=x;
    else
    {
        t[x]=y;
        if(h[x]==h[y])
            h[y]++;
    }
}
inline int cmp(muchie b1,muchie b2)
{
    if(b1.c<b2.c)
        return 1;
    return 0;
}
int main()
{
    int i,nr=0,v1,v2,x1,x2,ct=0,s=0;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        fin>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+m+1,cmp);
    for(i=1; i<=n; i++)
        h[i]=1;
    i=1;
    ct=0;
    nr=0;
    while(nr<n-1)
    {
        v1=a[i].x;
        v2=a[i].y;
        x1=Find(v1);
        x2=Find(v2);
        if(x1!=x2)
        {
            nr++;
            ct++;
            r[ct]=v2;
            ct++;
            r[ct]=v1;
            s=s+a[i].c;
            Union(x1,x2);
        }
        i++;
    }
    i=1;
    fout<<s<<"\n";
    fout<<nr<<"\n";
    while(i<=ct)
    {
        fout<<r[i]<<" "<<r[i+1]<<"\n";
        i=i+2;
    }
    return 0;
}