#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
typedef struct
{
    int X,Y,Cost;
}triplet;
vector <triplet> v,APM;
vector <vector<int>> comp;
int *r,N;
bool myFunction(triplet a,triplet b)
{
    return (a.Cost<b.Cost);
}
void initializare(int u)
{
    r[u]=u;
}
int reprez(int u)
{
    return r[u];
}
void reuneste(int u,int v)
{
    int r1=reprez(u);
    int r2=reprez(v);

    if(comp[r1].size() > comp[r2].size())
        swap(r1, r2);

    for(int k=0;k<comp[r1].size();k++)
    {
        if(r[k]==r2)
        {
            r[k]=r1;

        }
    }
}/*
bool exista_ciclu(vector <triplet> APM,int x,int y,int cost)
{
    triplet t;
    t.X=x;
    t.Y=y;
    t.Cost=cost;
    APM.push_back(t);
    int i;

    return 1;
}*/
int main()
{

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

    int i,M,cntAPM=0,costAPM=0;
    fin>>N>>M;
    r=new int[N];
    int *r;
    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);
        comp[i].push_back(i);
    }
    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;
}