#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int const NLIM = 200005;
int daddy[NLIM],n,m,h[NLIM];
struct apm
{
    int i,j,c;
} v[2*NLIM];
struct afisare
{
    int a,b;
} r[2*NLIM];
bool cmp(apm a,apm b)
{
    if(a.c<b.c)return true;
    return false;
}
int sef(int x)
{
    if(x!=daddy[x])x=sef(daddy[x]);
    return daddy[x];
}
void join(int x,int y)
{
    int t1=sef(x),t2=sef(y);
    daddy[t2]=t1;
}
int main()
{
    fin>>n>>m;
    unsigned int i;
    int j=0,s=0;
    for(i=1; i<=n; i++)daddy[i]=i;
    for(i=1; i<=m; i++)
    {
        fin>>v[i].i>>v[i].j>>v[i].c;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1; i<=m&&j<=n-2; i++)
    {
        if(sef(v[i].i)!=sef(v[i].j))
        {
            s+=v[i].c;
            join(v[i].i,v[i].j);
            j++;
            r[j].a=v[i].i;
            r[j].b=v[i].j;
            }
    }
    fout<<s<<endl<<j<<endl;
    for(i=1; i<=j; i++)
    {
        fout<<r[i].a<<" "<<r[i].b<<endl;
    }
    return 0;
}