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

using namespace std;

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

int n,m;
int tata[100005];
// vector <pair<int,int>> adj[1000];
vector <pair<int,int>> rez;
priority_queue <pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>> >edges;
int rad(int x){ 
    if(tata[x]==x){
        return x;
    }
    else{
        tata[x]=rad(tata[x]);
        return rad(tata[x]);
    }
}
void unite(int x,int y){
    int rx=rad(x);
    int ry=rad(y);
    if(rx<=ry){
        tata[ry]=rx;
    }
    else{
        tata[rx]=ry;
    }
}
bool check(int x,int y){
    int rx=rad(x);
    int ry=rad(y);
    if(rx==ry)
        return true;
        else
        return false;
}
int main(){
    in>>n>>m;
    for(int i=1;i<=n;i++){
        tata[i]=i;
    }
    int x,y,c;
    for(int i=1;i<=m;i++){
        in>>x>>y>>c;
        //adj[x].push_back({x,y});
        edges.push({c,{x,y}});
    }
    int cost=0;
    int contor=0;
    while(!edges.empty()){
        x=edges.top().second.first;
        y=edges.top().second.second;
        c=edges.top().first;
        if(check(x,y)==false){
            unite(x,y);
            cost+=c;
            rez.push_back({x,y});
            contor++;
        }
        edges.pop();
    }
    out<<cost<<'\n'<<contor<<'\n';
    for(auto it:rez){
        out<<it.first<<" "<<it.second<<'\n';
    }
    return 0;
}