#include <iostream>
#include <fstream>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("kruskal.in");
ofstream g("kruskal.out");
vector <tuple<int,int,int>> muchii;
vector <int> v[200001];
int n,m,c,x,i,y,nod1,nod2,nr,cost1,cost_total,p[200001],h[200001];
int Find(int x)
{
    while(p[x]!=x)
        x=p[x];
    return x;
}
int main()
{

    f>>n>>m;
    for(i=1;i<=n;++i)
    {
        p[i]=i;
        h[i]=1;
    }
    for(i=0;i<m;++i)
    {
        f>>x>>y>>c;
        muchii.push_back(make_tuple(c,x,y));

    }
    sort(muchii.begin(),muchii.end());

    for(i=0;i<m;++i)
    {
        nod1=get<1>(muchii[i]);
        nod2=get<2>(muchii[i]);
        cost1=get<0>(muchii[i]);
        int r1=Find(nod1);
        int r2=Find(nod2);
        if(r1!=r2)
        {

            if(h[r1]>h[r2])
            {
                p[r2]=r1;
            }
            else
                if(h[r1]<h[r2])
                    p[r1]=r2;
                else
                {

                    p[r1]=r2;
                    h[r2]++;
                }
            ++nr;
            v[nr].push_back(nod1);
            v[nr].push_back(nod2);
            cost_total+=cost1;

        }
    }
    g<<cost_total<<'\n';
    g<<nr<<'\n';
    for(i=1;i<=nr;++i)
    {
        g<<v[i][1]<<' '<<v[i][0]<<'\n';
    }


    return 0;
}