#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m;
struct triple{
    int cost;
    int a;
    int b;
};
bool cmp (const triple &a,const triple &b)
{
    return a.cost<b.cost;
}
vector<triple> A;
vector<int> T,R;
int find(int nod)
{
    if(nod==T[nod])
       return nod;
    else
     {
         T[nod]=find(T[nod]);
         return T[nod];
     }
}
long long total;
int nr;
vector<pair<int,int>> ans;
int main()
{
   cin>>n>>m;
   A.resize(m);
   T.resize(n+1);
   R.resize(n+1);
   for(int i=0;i<m;i++)
     cin>>A[i].a>>A[i].b>>A[i].cost;
   sort(A.begin(),A.end(),cmp);
   for(int i=1;i<=n;i++)
     T[i]=i;
   for(int i=0;i<m;i++)
   {
       int a=A[i].a;
       int b=A[i].b;
       int ra=find(a);
       int rb=find(b);
       if(ra!=rb)
       {
           ans.push_back({a,b});
           nr++;
           total=total+A[i].cost;
           if(R[ra]>R[rb])
              T[rb]=ra;
            else
            {
                T[ra]=rb;
                if(R[rb]==R[ra])
                   R[rb]++;
            }
           if(nr==nr-1)
             break;
       }
   }
   cout<<total<<'\n';
   cout<<nr<<'\n';
   for(int i=0;i<ans.size();i++)
     cout<<ans[i].first<<" "<<ans[i].second<<'\n';
   return 0;
}