#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct Muchie{
    int nod1,nod2,cost;
};
bool cmp(Muchie a, Muchie b)
{
    if(a.cost<b.cost)
        return 1;
    return 0;
}


int main()
{

    int N,M;
    in>>N>>M;
    vector<Muchie> A(M+1);
    vector <int> comp(N+1);
    vector <vector<int>>V(N+1);
    int i,cost=0,c=0;
    for(i=1;i<=N;i++)
    {
        V[i].push_back(i);
        comp[i]=i;
    }
    for(i=0;i<M;i++)
    {
        Muchie aux;
        in>>aux.nod1>>aux.nod2>>aux.cost;
        A[i] = aux;
    }
    sort(A.begin(),A.end(),cmp);
    vector<Muchie> sol;
    for(auto i: A)
    {
        if(comp[i.nod1]!=comp[i.nod2])
        {
             cost=cost+i.cost;
             sol.push_back(i);
             if(V[comp[i.nod1]].size()<V[comp[i.nod2]].size())
                for(auto j: V[comp[i.nod1]])
                {
                    V[comp[i.nod2]].push_back(j);
                    comp[j]=comp[i.nod2];
                    c=comp[j];
                }
              else
                for(auto j: V[comp[i.nod2]])
                {
                    V[comp[i.nod1]].push_back(j);
                    comp[j]=comp[i.nod1];
                    c=comp[j];
                }
        }
    }
    out<<cost<<"\n";
    out << sol.size() << "\n";
    for(auto val : sol)
        out << val.nod1 << " " << val.nod2 << "\n";
    return 0;
}