#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin ("apm.in");
ofstream fout("apm.out");
int n,m,dim[200002],tata[200002];

struct el
{
    int x,y,c;
} a[400002];
vector<int>sol;

int father (int x)
{
    if (x!=tata[x])
        tata[x]=father(tata[x]);
    return tata[x];
}

void unire (int x,int y)
{
    int tatax=father(x),tatay=father(y);
    if (dim[tatax]<dim[tatay])
    {
        dim[tatay]+=dim[tatax];
        tata[tatax]=tatay;
    }
    else
    {
        dim[tatax]+=dim[tatay];
        tata[tatay]=tatax;
    }
}

inline bool cmp (const el &a1,const el &a2)
{
    return a1.c<a2.c;
}

void apm ()
{
    int s=0,i;
    for (i=1;i<=n;++i)
        dim[i]=1,tata[i]=i;
    sort(a+1,a+m+1,cmp);
    for (i=1;i<=m;i++)
        if (father(a[i].x)!=father(a[i].y))
    {
        unire (a[i].x,a[i].y);
        sol.push_back(i);
        s+=a[i].c;
    }
    fout<<s<<'\n';
}

int32_t main()
{
    int i;
    fin>>n>>m;
    for (i=1; i<=m; i++)
        fin>>a[i].x>>a[i].y>>a[i].c;
    apm();
    fout<<n-1<<'\n';
    for (i=0;i<=n-2;i++)
        fout<<a[sol[i]].x<<' '<<a[sol[i]].y<<'\n';
    return 0;
}