#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
int n,m,a,b,c,ma[20010][20010],nr,k,p,cost;
bool viz[20010];
struct co{int x,y,c;}q[200010];
struct coo{int x,y;}cc[200010];

bool comp(co x,co y)
{
    return x.c>y.c;
}

int main()
{
    fin>>n>>m;
    for(;m;m--)
    {
        fin>>a>>b>>c;
        ma[a][b]=ma[b][a]=c;
    }
    viz[1]=1;
    nr=n-1;
    for(int i=1;i<=n;i++)
    {
        if(ma[1][i])
        {
            q[++k].x=1;
            q[k].y=i;
            q[k].c=ma[1][i];
        }
    }
    while(nr)
    {
        sort(q+1,q+k+1,comp);       ///in q[k] ii min
        int nod1=q[k].y;
        int nod2=q[k].x;
        ///int cost=q[k].c;
        k--;
        if(viz[nod1]==1&&viz[nod2]==0)         ///pt y
        {
            cc[++p].x=nod1;
            cc[p].y=nod2;
            cost+=ma[nod1][nod2];
            viz[nod2]=1;
            nr--;
            for(int i=1;i<=n;i++)
            {
                if(ma[nod2][i])
                {
                    k++;
                    q[k].x=nod2;
                    q[k].y=i;
                    q[k].c=ma[nod2][i];
                }
            }
        }
        else
        {
            if(viz[nod1]==0&&viz[nod2]==1)         ///pt y
            {
                cc[++p].x=nod2;
                cc[p].y=nod1;
                cost+=ma[nod1][nod2];
                viz[nod1]=1;
                nr--;
                for(int i=1;i<=n;i++)
                {
                    if(ma[nod1][i])
                    {
                        k++;
                        q[k].x=nod1;
                        q[k].y=i;
                        q[k].c=ma[nod1][i];
                    }
                }
            }
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(int i=1;i<=p;i++)
    {
        fout<<cc[i].x<<" "<<cc[i].y<<'\n';
    }
    return 0;
}