#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
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 <vector<int>> Graf(n+1);
    vector <int> comp(n+1);
    for(int i=1;i<=n;i++)
    {
        Graf[i].push_back(i);
        comp[i]=i;
    }

   for(int i=0;i<m;i++)
   {
       Muchie aux;
       in>>aux.nod1>>aux.nod2>>aux.cost;
       A[i]=aux;
   }
   double 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[i.nod1].size()<Graf[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];
                }
       }
   }
   out<<cost<<"\n"<<sol.size()<<"\n";
   for(auto i: sol)
   {
       out<<i.nod1<<" "<<i.nod2<<"\n";
   }
}