#include <fstream>
#include <algorithm>
#define MMAX 400004
#define NMAX 200002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
{
    int x,y;
    double cost;
};

muchie G[MMAX];
muchie APM[NMAX];
double cost_APM;
int conex[NMAX];
int n,m;
int nrm;

bool criteriu(muchie x,muchie y);
void citire();

int main()
{
    citire();
    sort(G+1,G+m+1,criteriu);
    int i,j,minim,maxim;
    for(i=1;nrm<=n;i++)
    {
        if(conex[G[i].x]!=conex[G[i].y])
        {
            cost_APM+=G[i].cost;
            APM[++nrm]=G[i];
            if(G[i].x>=G[i].y)
            {
                minim=G[i].y;
                maxim=G[i].x;
            }
                else
                {
                    minim=G[i].x;
                    maxim=G[i].y;
                }
            for(j=1;j<=n;j++)
            {
                if(conex[j]==conex[maxim])
                {
                    conex[j]=conex[minim];
                }
            }
        }
    }

    fout<<cost_APM<<"\n";
    fout<<nrm<<"\n";
    for(i=1;i<=nrm;i++)
        fout<<APM[i].x<<" "<<APM[i].y<<"\n";
    return 0;
}

bool criteriu(muchie x,muchie y)
{
    return x.cost<=y.cost;
}

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