#include <fstream>
#include <algorithm>
#define maxn 400005
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,gr[maxn],x[maxn],y[maxn],c[maxn],ins[maxn],ans,ord[maxn],h[maxn];
bool cmp(int i,int j)
{
    return(c[i]<c[j]);
}
int findd(int i)
{
    int y,r=i;
    while(gr[r]!=r)
        r=gr[r];
    while(i!=gr[i])
    {
        y=gr[i];
        gr[i]=r;
        i=y;
    }
    return r;
}
void reunire(int i, int j)
{
    gr[findd(i)]=findd(j);
}
int main()
{
    int i,j,l=0;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i]>>c[i];
        ins[i]=i;
    }
    for(i=1;i<=n;i++)
        gr[i]=i;
    sort(ins+1,ins+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        if(findd(x[ins[i]])!=findd(y[ins[i]]))
        {
            reunire(x[ins[i]],y[ins[i]]);
            ans+=c[ins[i]];
            l++;
            ord[l]=ins[i];
        }
    }
    cout<<ans<<'\n'<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        cout<<x[ord[i]]<<" "<<y[ord[i]]<<'\n';
    return 0;
}