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

using namespace std;

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


vector <int> l[200001];
pair <int , int> v[400001],afis[400001];
int cost[400001];
int tata[200001];


void viz0(){
    for(int i=1;i<=200001;i++)
            tata[i]=-1;
}
    

void sortare(int m){
    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
            if(cost[j]<cost[i])
                swap(cost[i],cost[j]),swap(v[i],v[j]);
}

void afisare(int s, int k,int n){
    int vizi[101]={0};
    fout<<s<<endl<<k<<endl;
    for(int i=1;i<=n;i++){
        for(int j:l[i])
            if(vizi[i]+vizi[j]<2){
                fout<<i<<" "<<j<<endl;
                vizi[i]=1;
                vizi[j]=1;
            }
                
    }
}

int find_root(int node){
    if(tata[node]<0)
        return node;
    int root=find_root(tata[node]);
    tata[node]=root;
    return root;
}

void roots_union(int x, int y){
    int r_x=find_root(x);
    int r_y=find_root(y);
    if(tata[r_x]<tata[r_y]){
        swap(r_y,r_x);
    }
    tata[r_y]+=tata[r_x];
    tata[r_x]=r_y;
}

int main() {
    int n,m;
    int x,y,z;
    int s=0,k=0;
    viz0();
    
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        
        fin>>x>>y>>z;
        v[i]={x,y};
        cost[i]=z;
        
    }
    sortare(m);
    
    for(int i=1;i<=m;i++){
        if(find_root(v[i].first)!=find_root(v[i].second)){
            k++;
            s+=cost[i];
            afis[k].first=v[i].second;
            afis[k].second=v[i].first;
            roots_union(v[i].first,v[i].second);
        }
    }
    fout<<s<<endl<<k<<endl;
    for(int i=1;i<=k;i++)
        fout<<afis[i].first<<" "<<afis[i].second<<endl;
    return 0;
}