#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e5 + 5, mmax = 4e5 + 5;

int N, M, k, x, y, z, t[nmax], h[nmax], cost, cnt;
typedef struct poz2{
    int a, b;
}student2;
vector < student2 > ans;

typedef struct poz{
    int a, b, c;
}student;
student v[mmax];

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

////////////////////////////////////////////////////

bool comp(student x, student y){
    if(x.c < y.c){
        return 1;
    }
    return 0;
}


int Radacina(int node){
    
    if(t[node] == node){
        return node;
    }else{
        int r = Radacina(t[node]);
        t[node] = r;
        
        return r;
    }
    
}


void Unire(int a, int b){
    
    a = Radacina(a)  , b = Radacina(b);
    
    if(h[a] < h[b]){
        t[a] = b;
        h[b] += h[a];
    }else{
        t[b] = a;
        h[a] += h[b];
    }
    
}

int main()
{
    
    ios_base::sync_with_stdio(0);
    fin.tie(0);
    fout.tie(0);
    
    fin>>N>>M;
    
    for(int i=1;i<=M;i++){
        fin>>v[i].a>>v[i].b>>v[i].c;
    }
    
    for(int i=1;i<=N;i++){
        t[i] = i;
        h[i] = 1;
    }
    
    sort(v+1 , v+M+1 , comp);
    
    
    for(int i=1;i<=M;i++){
        if(Radacina(v[i].a) != Radacina(v[i].b)){
            Unire(v[i].a , v[i].b);
            
            cost += v[i].c;
            cnt++;
            ans.push_back({v[i].a , v[i].b});
        }
    }
    
    fout<<cost<<"\n";
    fout<<cnt<<"\n";
    
    for(int i=0;i<cnt;i++){
        fout<<ans[i].a<<" "<<ans[i].b<<"\n";
    }
    
    
}