#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <fstream>
#include <functional>
// #include <priority_queue>
using namespace std;

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


int n,m;
struct muchie{
    int v , cost;
    bool operator()(const muchie& a, const muchie& b){
        return a.cost>b.cost;
    }
};
priority_queue<muchie, vector<muchie>, muchie> pq;  

vector<vector<muchie>> adj;
vector<int> vizitat;
vector<vector<int>> apcm;


int main(){
    in>>n>>m;
    adj.assign(n+1, vector<muchie>());
    vizitat.assign(n+1, 0);
    for(int i=0;i<m;i++){
        int x, y, c;
        in>>x>>y>>c;
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
    }
    
 
    int rezultat=0;
    
    pq.push({1,0});
    int anterior=1;
    while(!pq.empty()){
        int u=pq.top().v;
        int c=pq.top().cost;
        pq.pop();
        
        if(vizitat[u]==1){continue;}
        vizitat[u]=1;
        rezultat+=c;  
        if(u!=1){
            apcm.push_back({anterior, u});  
            anterior=u;
        }

        for(auto v: adj[u]){
            if(vizitat[v.v]==0){
                pq.push(v);
                
            }
        }

    }
    out<<rezultat<<endl;
    out<<apcm.size()<<endl;
    for(long unsigned int i=0;i<apcm.size();i++){
        out<<apcm[i][0]<<" "<<apcm[i][1]<<endl;
    }
    out.flush();


    return 0;
}