#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int nmax=200005;
const int mmax=400005;
struct muchie {int x,y,cost;} a[mmax];
int parinte[nmax],cmin,siz_arb,parx,pary,n,m,i;
vector <int> ras[3];

bool cmp (muchie A , muchie B)
{
    return A.cost<B.cost;
}

int find_parent (int nod)
{
    if (parinte[nod]==nod)
        return nod;
    else
        parinte[nod]=find_parent(parinte[nod]);
    return parinte[nod];
}

void unite (int nod_A, int nod_B)
{
    int par_A,par_B;
    par_A=parinte[nod_A];
    par_B=parinte[nod_B];
    parinte[par_A]=par_B;
}

int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
        f>>a[i].x>>a[i].y>>a[i].cost;

    for (i=1;i<=n;i++)
        parinte[i]=i;

    sort(a+1,a+m+1,cmp);

    i=1;
    while (siz_arb!=n-1)
    {
        parx=a[i].x;
        pary=a[i].y;
        parx=find_parent(parx);
        pary=find_parent(pary);

        if (parx!=pary)
        {
           cmin+=a[i].cost;
           unite(parx,pary);
           siz_arb++;
           ras[1].push_back(a[i].y);
           ras[2].push_back(a[i].x);
        }

        i++;
    }

    g<<cmin<<'\n';
    g<<n-1<<'\n';

    for (i=0;i<n-1;i++)
        g<<ras[1][i]<<" "<<ras[2][i]<<'\n';

    return 0;
}