#include<bits/stdc++.h>
using namespace std;

struct edge{
    int x, y;
    int cost;
};

struct cluster{
    vector<int>noduri;
    vector<edge>muchii; //strict OUTgoing
    
};


void AddToVector(vector<edge>&v, edge k){
    v.push_back(k);
    int poz=v.size()-1;
    while(v[poz].cost<v[poz-1].cost && poz>0){
        swap(v[poz],v[poz-1]);
        poz--;
    }
}

bool IsInsideEdge(vector<int>v, edge k){
    for(int i=0;i<v.size();i++){
        if(v[i]==k.y){
            return true;
        }
    }
    return false;
}

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

int main(){
    int n, m, x, y, c;
    in>>n>>m;
    vector<cluster>G(n);
    vector<edge>apm;
    
    // out<<"Test 1 \n";
    
    for(int i=0;i<n;i++)
    G[i].noduri.push_back(i);
    
    // out<<"Test 1 \n";
    
    for(int i=0;i<m;i++){
        in>>x>>y>>c;
        x--;
        y--;
        edge ed;
        ed.x=x;
        ed.y=y;
        ed.cost=c;
        AddToVector(G[x].muchii, ed);
        ed.x=y;
        ed.y=x;
        AddToVector(G[y].muchii, ed);
    }
    
    // out<<"Test 1";
    
    while(G.size()>1){
        
        int par=G.back().muchii[0].y; //indexul clusterului caruia ii atasam ultimul element, conectat prin muchie minima
        
        apm.push_back(G.back().muchii[0]); //muchia minima in apm
        
        for(int i=0;i<G.back().muchii.size();i++){
            
            for(int j=0;j<G[par].muchii.size();j++){
            if(IsInsideEdge(G.back().noduri, G[par].muchii[j])){
                G[par].muchii.erase(G[par].muchii.begin()+j);       //scoatem muchiile interne
            }
            }
            if(!IsInsideEdge(G[par].noduri ,G.back().muchii[i])){
                
                G[par].muchii.push_back(G.back().muchii[i]);        //adaugam muchiile outgoing in noul cluster
            }
        }
        
        for(int i=0;i<G.back().noduri.size();i++){
            
            // cout<<"test 1"<<flush;
            
            G[par].noduri.push_back(G.back().noduri[i]); //aduagam nodurile clusterului vechi in noul clusterc  //se incurca la al 5-lea element
            
        }
    
        
        G.pop_back();               //why have the gods forsaken us
                                                                            //  TODO                                        
                                                                            //  Adaugat muchiile outgoing in noul cluster DONE
                                                                            //  Retinut muchiile interne din apm DONE
       }                                                                    //  adaugat indexle noilor elemente la cluster DONE
       
    //   out<<"Test 1";
       
    int rasp=0;
    for(int i=0;i<apm.size();i++){
        rasp+=apm[i].cost;
    }
    out<<rasp<<"\n";
    out<<apm.size()<<"\n";
    for(int i=0;i<apm.size();i++){
        out<<apm[i].x<<" "<<apm[i].y<<"\n";
    }
}