#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));
        }
    }
    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 vizitati[200001],j;
       int l=1;
       vizitati[0]=1;
       A.n=1;
       int i=1,minim,k,p=0;
       viz[i]=1;
       for(j=0;j<this->A[i].size();j++)
         {
             pair<pereche,int> pdp;
            pdp=make_pair(make_pair(i,this->A[i][j].first),this->A[i][j].second);
            minHeap.push(pdp);
        }
       while(A.n!=this->n)
       {

           pair<pereche,int> pdp2;
           while(viz[minHeap.top().first.first] && viz[minHeap.top().first.second])
           minHeap.pop();
           pdp2=minHeap.top();
           A.A[minHeap.top().first.first].push_back(make_pair(minHeap.top().first.second,minHeap.top().second));
           viz[pdp2.first.second]=1;
           minHeap.pop();
           viz[pdp2.first.second]=1;
           p=p+pdp2.second;
           A.n++;
           A.m++;

           for(i=0;i<this->A[pdp2.first.second].size();i++)

       {
           if(viz[this->A[pdp2.first.second][i].first]==0)
            {pair<pereche,int> pdp;
            pdp=make_pair(make_pair(pdp2.first.second,this->A[pdp2.first.second][i].first),this->A[pdp2.first.second][i].second);
           minHeap.push(pdp);
           }
       }


       }
       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();
}