#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("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;
    fin >> n >> m;
    vector <Muchie> A(m);
    vector <vector<int>> Graf(n);
    vector <int> comp(n);
    for(int i=0;i<n;i++)
    {
        Graf[i].push_back(i);
        comp[i]=i;
    }
    for(int i=0;i<m;i++)
    {
        Muchie aux;
        fin >> aux.nod1 >> aux.nod2 >> aux.cost;
        aux.nod1--; aux.nod2--;
        A[i]=aux;
    }
    int cost=0;
    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(Graf[comp[i.nod1]].size()<Graf[comp[i.nod2]].size())
            {
                for(auto j: Graf[comp[i.nod1]])
                {
                    Graf[comp[i.nod2]].push_back(j);
                    comp[j]=comp[i.nod2];
                }
            }
            else
                for(auto j: Graf[comp[i.nod2]])
                {
                     Graf[comp[i.nod1]].push_back(j);
                     comp[j]=comp[i.nod1];
                }
        }
   }
   fout<<cost<<"\n"<<sol.size()<<"\n";
   for(auto i: sol)
   {
       fout<<i.nod1+1<<" "<<i.nod2+1<<"\n";
   }
   return 0;
}