#include <iostream>
#include <fstream>
#include <vector>
#include <queue>


using namespace std;
typedef pair<int , int > pereche;
int viz[200001];
int viz2[200001];

struct comparator {
 bool operator()(pair<pereche,int> i,pair<pereche,int>  j) {
 return i.second > j.second;
 }
};
priority_queue< pair<pereche,int>, std::vector<pair<pereche,int> >, comparator> minHeap;
class graf
{   int n , m,c;
    vector <pair<int,int> > A[50000];
public:


    void citire(char *numfis)
    {  int i;
        ifstream f(numfis);
        f>>n;
        f>>m;
        for(i=0;i<m;i++)
        {   int a ,b,c;
            f>>a>>b>>c;
            A[a].push_back(make_pair(b,c));
            A[b].push_back(make_pair(a,c));
            pair<pereche,int> pdp;
            pdp=make_pair(make_pair(a,b),c);
           minHeap.push(pdp);
        }
    }
    void afisare()
    {  int i , j;
        for(i=1;i<=n;i++)
        {   cout<<"\n"<<i<<": ";
            for(j=0;j<A[i].size();j++)
                cout<<A[i][j].first<<" ";
        }
    }
    void vizita(int i)
    { int j;

        for(j=0;j<this->A[i].size();j++)
            {
                int a=A[i][j].first;
                if(viz[A[i][j].first]!=1)
                {viz[A[i][j].first]=1;
                this->vizita(a);
                }
            }

    }
    void prim()
    {
       graf A;
       int l=1,i=1;
       int tata[200001];
       for(i=1;i<=n;i++)
         tata[i]=i;
       A.n=1;
       A.m=1;
       int minim,k,p=0;
      viz[minHeap.top().first.first]=1;
      viz[minHeap.top().first.second]=1;
      A.A[minHeap.top().first.first].push_back(make_pair(minHeap.top().first.second,minHeap.top().second));
      A.A[minHeap.top().first.second].push_back(make_pair(minHeap.top().first.first,minHeap.top().second));
      p=p+minHeap.top().second;
      minHeap.pop();

       while(A.n!=this->n-1)
       {

           pair<pereche,int> pdp2;


           while(tata[minHeap.top().first.first]== tata[minHeap.top().first.second])
             minHeap.pop();



             pdp2=minHeap.top();
                if(viz[minHeap.top().first.first]==1 && viz[minHeap.top().first.second]==1)
           {
               A.n--;
               A.m--;
           }
             pdp2=minHeap.top();

               if(viz[minHeap.top().first.first]==1 && viz[minHeap.top().first.second]==0)
               {
                   viz[minHeap.top().first.second]=1;
                   p=p+pdp2.second;
                   A.A[minHeap.top().first.first].push_back(make_pair(minHeap.top().first.second,minHeap.top().second));
                   A.A[minHeap.top().first.second].push_back(make_pair(minHeap.top().first.first,minHeap.top().second));
                   A.vizita(pdp2.first.second);
               }
               if(viz[minHeap.top().first.first]==0 && viz[minHeap.top().first.second]==1)
               {
                   p=p+pdp2.second;
                   viz[minHeap.top().first.first]=1;
                   A.A[minHeap.top().first.first].push_back(make_pair(minHeap.top().first.second,minHeap.top().second));
                    A.A[minHeap.top().first.second].push_back(make_pair(minHeap.top().first.first,minHeap.top().second));
                   A.vizita(minHeap.top().first.first);
               }
               if(viz[minHeap.top().first.first]==0 && viz[minHeap.top().first.second]==0)
               {
                  p=p+pdp2.second;
                   A.A[minHeap.top().first.first].push_back(make_pair(minHeap.top().first.second,minHeap.top().second));
                    A.A[minHeap.top().first.second].push_back(make_pair(minHeap.top().first.first,minHeap.top().second));
               }

           pdp2=minHeap.top();
           minHeap.pop();


           A.n++;
           A.m++;




       }
       A.c=p;
       A.afisareapm();

    }
    void afisareapm()
    {   int i , j;
        ofstream g("apm.out");
        g<<c<<"\n";
        g<<m<<"\n";
        for(i=1;i<=n;i++)
            for(j=0;j<A[i].size();j++)
        {
            if(viz2[i]<A[i].size() && viz2[A[i][j].first]<A[A[i][j].first].size())
            {g<<i<<" "<<A[i][j].first;
            g<<"\n";
            viz2[i]++;
            viz2[A[i][j].first]++;
            }
        }

    }
};

int main()
{   graf G;
    ifstream f("apm.in");
    G.citire("apm.in");

    G.prim();
}