#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <tuple>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX = 100001;
int dad[NMAX], rnk[NMAX];
int n, m, s, k;
vector<tuple<int, int, int>> G;
vector<pair<int, int>> edges;

void citire()
{
    fin>>n>>m;
    for(int i=0; i<m; ++i)
    {
        int x, y, c;
        fin>>x>>y>>c;
        G.push_back(make_tuple(c, x, y));
    }
    sort(G.begin(), G.end());
}

void init()
{
    for(int i=1; i<=n; ++i)
        dad[i]=i;
}

int dofind(int nod)
{
    if(dad[nod]!=nod)
    {
        int repr=dofind(dad[nod]);
        dad[nod]=repr;
        return repr;
    }
    return dad[nod];
}

void dounion(int n1, int n2)
{
    int rx=dofind(n1), ry=dofind(n2);
    if(rnk[rx]==rnk[ry])
    {
        dad[rx]=ry;
        rnk[ry]++;
    }
    else if(rnk[rx]<rnk[ry]) dad[rx]=ry;
    else dad[ry]=rx;
}

void cruisecall()
{
    init();
    for(int i=0; i<m; ++i)
    {
        int n1=get<1>(G[i]), n2=get<2>(G[i]);
        if(dofind(n1)!=dofind(n2))
        {
            s+=get<0>(G[i]);
            dounion(n1, n2);
            edges.push_back(make_pair(n1, n2));
        }
    }
    fout<<s<<"\n";
    fout<<n-1<<"\n";
    for(int i=0; i<edges.size(); ++i)
        fout<<edges[i].first<<" "<<edges[i].second<<"\n";

}

int main()
{
    citire();
    cruisecall();
}