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


using namespace std;
typedef pair<int , int > pereche;
int viz[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[200001];
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 prim()
    {
       graf A;
       int l=1,i=1;
       int tata[200001];
       for(i=1;i<=n;i++)
         tata[i]=i;
       A.n=1;
       int minim,k,p=0;


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

           pair<pereche,int> pdp2;


           while(tata[minHeap.top().first.first]== tata[minHeap.top().first.second])
             minHeap.pop();
           if(tata[minHeap.top().first.first]!= tata[minHeap.top().first.second])
           {
               A.A[minHeap.top().first.first].push_back(make_pair(minHeap.top().first.second,minHeap.top().second));

                         if(tata[minHeap.top().first.first]<tata[minHeap.top().first.second])
                            tata[minHeap.top().first.first]=tata[minHeap.top().first.second];
                        else
                           tata[minHeap.top().first.second]=tata[minHeap.top().first.first];
           }
           pdp2=minHeap.top();
           viz[pdp2.first.second]=1;
           viz[pdp2.first.first]=1;
           minHeap.pop();

           p=p+pdp2.second;
           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++)
        {
            g<<i<<" "<<A[i][j].first;
            g<<"\n";
        }

    }
};

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

    G.prim();
}