/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

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

using namespace std;

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

vector<pair<int, int>> muchii, outv;

struct cmp {
    bool operator() (pair<int, int> a, pair<int,int> b) {  
        if(a.first == b.first) 
          return muchii[a.second]>=muchii[b.second];
        return a.first >= b.first;
    }
};

int main()
{
    int n, m, x, y, k;
    
    fin >> n >> m;
    
    priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;
    
    for(int i=0; i<m; i++) {
        fin >> x >> y >> k;
        
        muchii.push_back({x,y});
        pq.push({k,i});
        
    }
    
    
    vector<int> vis(n,0);
    int c = 0, np=0, npn=0;
    int cnt = 0;
    while(!pq.empty() && np<(n-1) && npn <n){
        pair<int, int> p, m;
        
        p = pq.top();
        
        m = muchii[p.second];
       
        if((!vis[m.first] || !vis[m.second]) || (vis[m.first]!=vis[m.second]))
        {
            
            if((!vis[m.first] && !vis[m.second])) {
                
              ++cnt, vis[m.first] = vis[m.second] = cnt;
              
              
            }
            else if(vis[m.first]!=vis[m.second]) {
              
              int a = m.first, b = m.second;
              if(!vis[a]) vis[a] = vis[b];
              else if(!vis[b]) vis[b] = vis[a];
              
              else {
                int cvb = vis[b];
                for(int i=1; i<=n; i++) 
                     if(vis[i]==cvb) vis[i] = vis[a];
              }
              
            }
            
            cout << m.first << m.second << vis[m.first] << vis[m.second] << endl;
                
            if(!vis[m.first]) npn++;
            if(!vis[m.second]) npn++;
       
            c+=p.first;
            np++;
            outv.push_back(m);
        }
        
        pq.pop();
    }
    
    fout << c << endl;
    fout << outv.size() << endl;
    
    for(int i=0; i<outv.size();i++) 
        fout << outv[i].first  << " " << outv[i].second << endl;

    
    return 0;
}