#include <fstream>
#include <iostream>
#include <queue>
#define fi first
#define se second

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct cmp {
bool operator()(pair<int,int> fi, pair<int,int> se) {
     
     return fi.fi > se.fi;
}  
};

const int NMAX = 100000;
vector < pair<int,int> > A[NMAX];
typedef vector< pair<int,int>   > :: iterator vptr;
priority_queue < pair<int,int>, vector<pair<int,int> > , cmp  > H;
int N,M,apm;

void readGraph() {
     
     fin>>N>>M;
     
     for(int i = 0 ; i < M; ++i) {
                 
                 int x,y,c;
                 fin>>x>>y>>c;
                 --x, --y;
                 
                 A[x].push_back( make_pair(y,c) );
                 A[y].push_back( make_pair(x,c) );
             }
}

int T[NMAX];
bool inTree[NMAX];

void prim() {
     
     int d[NMAX]; 
     pair<int,int> min;
     
     memset(d,0x7f,sizeof d);
     
     d[0] = 0;
     
     
     T[0] = -1;
     
     H.push( make_pair(0,0) ); //fi - nod, se - cost
     
     
     for(int i = 0; i < N; ++i) {
             
             while(!H.empty() && inTree[H.top().se]) {
              H.pop();
             }           
             
             min = H.top();  H.pop();
             
             inTree[min.se] = 1;
             
             //cout<<min.se+1<<' '<<min.fi<<endl;
             apm += min.fi;
             
             for(vptr p = A[min.se].begin(); p != A[min.se].end(); ++p) 
               if(!inTree[p->fi] && d[p->fi] > p->se)
               {
                                 d[p->fi] = p->se;
                                 T[p->fi] = min.se;
                                 H.push( make_pair( p->se, p->fi) );
               }
                      
                      
                      }       
     }
     
void writeTree() {
     
     fout<<apm<<endl;
     fout<<N-1<<endl;
     
    for(int i = 1 ; i < N; ++i)
    
     
            fout<<i+1<<' '<<T[i]+1<<endl;
}
     

int main() {
    
           readGraph();
           prim();
           
           writeTree();

           return 0;
}