#include <fstream>
#include <algorithm>

using namespace std;

ifstream fi("apm.in");
ofstream fo("apm.out");

struct muchie { int v1,v2,cost;};

int n,m;
muchie E[400002];

int P[200002];
int NR[200002];
int REZ[400002];

int cmp(muchie a, muchie b)
{
    return a.cost<b.cost;
}

int parinte(int v)
{
    while (P[v]!=v)
        v=P[v];
    return v;
}

int main()
{
    fi>>n>>m;
    for(int i=1;i<=m;i++)
        fi>>E[i].v1>>E[i].v2>>E[i].cost;
    sort(E+1,E+m+1,cmp);
    for (int i=1;i<=n;i++)
    {
        P[i]=i;
        NR[i]=1;
    }
    int s=0;
    int nr=0;
    for(int i=1;i<=m;i++)
    {
        int p1=parinte(E[i].v1);
        int p2=parinte(E[i].v2);
        if (p1!=p2)
        {
            nr++;
            REZ[nr]=i;
            s=s+E[i].cost;
            /// unificare de arbori
            if (NR[p1]<=NR[p2])
            {
                NR[p2]+=NR[p1];
                P[p1]=p2;
            }
            else
            {
                NR[p1]+=NR[p2];
                P[p2]=p1;
            }
        }
    }
    fo<<s<<endl;
    fo<<n-1<<endl;
    for(int i=1;i<=nr;i++)
        fo<<E[REZ[i]].v1<<" "<<E[REZ[i]].v2<<endl;
    fi.close();
    fo.close();
    return 0;
}