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


using namespace std;
typedef pair<int , int > pereche;
int tata[200001],rang[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<<" ";
        }
    }
    int radacina(int i)
{
    if(i==tata[i]) return i ;
    tata[i] = radacina (tata[i]) ;
    return tata[i] ;
}
    void prim()
    {
       graf A;
       int p=0;
       for(int i=1;i<=n;i++)
        {
            tata[i]=i;
            rang[i]=i;
        }
       A.n=1;
       while(A.n!=this->n)
       {
           pair<pereche,int> pdp2;
             pdp2=minHeap.top();
             if(radacina(minHeap.top().first.first)!=radacina(minHeap.top().first.second))
                    {
                        A.A[minHeap.top().first.first].push_back(make_pair(minHeap.top().first.second,minHeap.top().second));
                        A.n++;
                        A.m++;
                        p=p+minHeap.top().second;
                        if(rang[radacina(minHeap.top().first.first)]==rang[radacina(minHeap.top().first.second)])
                            rang[radacina(minHeap.top().first.first)]++;
                        else
                            if(rang[radacina(minHeap.top().first.first)]>rang[radacina(minHeap.top().first.second)])
                                tata[radacina(minHeap.top().first.second)]=radacina(minHeap.top().first.first);
                            else
                                tata[radacina(minHeap.top().first.first)]=radacina(minHeap.top().first.second);
                    }
             minHeap.pop();


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