#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;
    }
    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];
                }
        }
   }
   out<<cost<<"\n"<<sol.size()<<"\n";
   for(auto i: sol)
   {
       out<<i.nod1<<" "<<i.nod2<<"\n";
   }
}