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

                              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");


struct cmp {
    bool operator() (pair<int, int> a, pair<int,int> b) {   
        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;
    
    vector<pair<int, int>> muchii, outv;
    
    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;
    
    while(!pq.empty() && np<n){
        pair<int, int> p, m;
        p = pq.top();
        
        m = muchii[p.second];
      
        if(!vis[m.first] || !vis[m.second])
        {
            if(!vis[m.first]) np++, vis[m.first] = 1;
            if(!vis[m.second]) np++, vis[m.second] = 1;
            
            vis[m.first] = vis[m.second] = 1;
            c+=p.first;
            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;
}