#include<iostream>
#include<fstream>
#include<climits>
#include<vector>

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

#define nrm 200010
const int oo=(1<<31)-1;
int n,m,total=0;
struct muchie
{
    int x,y,cost;
}mu[nrm];
int arb[nrm];
vector<pair<int,int> > rezultat;

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>mu[i].x>>mu[i].y>>mu[i].cost;
    }
}

void afisare()
{
    fout<<total<<'\n';
    fout<<n-1<<'\n';
    for(int i=0;i<rezultat.size();i++)
    {
        fout<<rezultat[i].first<<" "<<rezultat[i].second<<'\n';
    }
}


int main ()
{
    int pozitie,arbcrt,MIN=oo;

    citire();

    for(int i=1;i<=n;i++)
        arb[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(MIN>mu[i].cost)
        {
            MIN=mu[i].cost;
            pozitie=i;
        }
    }
    arb[mu[pozitie].x]=arb[mu[pozitie].y];
    arbcrt=arb[mu[pozitie].y];
    mu[pozitie].cost=oo;
    total=total+MIN;
    rezultat.push_back(make_pair(mu[pozitie].x,mu[pozitie].y));
    for(int k=2;k<=n-1;k++)
    {
        MIN=oo;
        for(int i=1;i<=m;i++)
        {
            if((arbcrt==arb[mu[i].x] || arbcrt==arb[mu[i].y]))
            {
                if(MIN>mu[i].cost && arb[mu[i].y]!=arb[mu[i].x])
                {
                    MIN=mu[i].cost;
                    pozitie=i;
                }
            }
            /*if(MIN>mu[i].cost)
            {
                if((arbcrt==arb[mu[i].x] || arbcrt==arb[mu[i].y]) && arb[mu[i].y]!=arb[mu[i].x])
                {
                    MIN=mu[i].cost;
                    pozitie=i;
                }
            }*/
        }
        total=total+MIN;
        arb[mu[pozitie].x]=arbcrt;
        arb[mu[pozitie].y]=arbcrt;
        rezultat.push_back(make_pair(mu[pozitie].x,mu[pozitie].y));
    }
    afisare();
    fin.close();
    fout.close();
    return 0;
}