#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
typedef struct
{
    int X,Y,Cost;
}triplet;
vector <triplet> v,APM;
int N;
int r[200001],viz[200001];
bool myFunction(triplet a,triplet b)
{
    return (a.Cost<b.Cost);
}
void initializare(int u)
{
    r[u]=u;
}
int reprez(int u)
{
    if(r[u]==u)
        return r[u];
    else
        return r[u]=reprez(r[u]);
}
void reuneste(int u,int v)
{
    int r1=reprez(u);
    int r2=reprez(v);
    if(viz[r1]>viz[r2])
    {
        r[r2]=r1;
        viz[r1]=viz[r1]+viz[r2];
    }
    else
    {
        r[r1]=r2;
        viz[r2]=viz[r2]+viz[r1];
    }
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    triplet T;
    int i,M,cntAPM=0,costAPM=0;
    fin>>N>>M;
    for(i=0;i<M;i++)
    {
        fin>>T.X>>T.Y>>T.Cost;
        v.push_back(T);
    }
    sort(v.begin(),v.begin()+M,myFunction);
    for(i=1;i<=N;i++)
    {
        initializare(i);
        viz[i]=1;
    }
    for(i=0;i<M;i++)
    {
        if(reprez(v[i].X)!=reprez(v[i].Y))
        {
            costAPM+=v[i].Cost;
            APM.push_back(v[i]);
            reuneste(v[i].X,v[i].Y);
        }
    }
    fout<<costAPM<<'\n';
    fout<<APM.size()<<'\n';
    for(i=0;i<APM.size();i++)
    {
        fout<<APM[i].X<<' '<<APM[i].Y<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}