#include <iostream>
#include <fstream>

#define dim 200005

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

int t[dim],rang[dim];

struct muchii{
    int x,y,c;
}muc[dim*2],out[dim*2-1];

int findroot(int x)
{
    int root=t[x];
    while(root!=t[root])
    {
        root=t[root];
    }
    while (t[x]!=x)
    {
        int aux=t[x];
        t[x]=root;
        x=aux;
    }
    return root;
}

void reuniune(int x,int y)
{
    if (rang[y]<rang[x])
        t[findroot(y)]=findroot(x);
    else
        t[findroot(x)]=findroot(y);
    if (rang[y]==rang[x])
        rang[y]++;
}

int main()
{
    int n,m;
    fin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        t[i]=i;
        rang[i]=1;
    }
    for (int i=1; i<=m; i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        muc[i].x=x;
        muc[i].y=y;
        muc[i].c=cost;
        /*for (int aux=i;aux>=2;aux--)
            if (muc[aux].c<muc[aux-1].c)
            {
                muchii auxx=muc[aux];
                muc[aux]=muc[aux-1];
                muc[aux-1]=auxx;
            }*/
    }
    int ok=0;
    while(ok==0)
    {
        ok=1;
        for (int i=1;i<m;i++)
            if (muc[i].c>muc[i+1].c)
            {   ok=0;
                muchii aux=muc[i];
                muc[i]=muc[i+1];
                muc[i+1]=aux;
            }
    }
    int costfinal=0,k=1;
    for (int muchie=1;muchie<=m;muchie++)
        if (findroot(muc[muchie].x)!=findroot(muc[muchie].y))
        {
            reuniune(muc[muchie].x,muc[muchie].y);
            costfinal+=muc[muchie].c;
            out[k++]=muc[muchie];
        }
    fout<<costfinal<<'\n'<<n-1<<'\n';
    for (int i=1;i<=n-1;i++)
        fout<<out[i].x<<' '<<out[i].y<<'\n';
    return 0;
}