#include <iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define nmax 200001
#define mmax 400001

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct mm{
    int k, a, b;
};
struct conexe{
    int cmp;
    bool status = false;
};

int n, m;
vector<mm> muchii;
vector<int>graf[nmax];
conexe comp[nmax];
vector<int>rez;

bool compare(mm a, mm b){
    return (a.k < b.k);
}

void u1_v0(int a, int b){
    comp[b].status = true;
    comp[b].cmp = comp[a].cmp;
}

void u1_v1_dfs(int nod, int componenta){
    comp[nod].cmp = componenta;
    for(int i = 0; i < graf[nod].size(); ++i){
        int vecin = graf[nod][i];
        if(comp[vecin].cmp != componenta){
            u1_v1_dfs(vecin, componenta);
        }
    }

}
int main()
{
    in>>n>>m;
    for(int i = 0; i < m; ++i){
        mm x;
        in>>x.a>>x.b>>x.k;
        muchii.push_back(x);
    }
    sort(muchii.begin(), muchii.end(), compare);

    for(int i = 1; i <= n; ++i){
        comp[i].cmp = i;
    }
    int sum = 0, nr_muchii = 0;
    for(int i = 0; i < m; ++i){
        if(nr_muchii == n - 1)
            break;
        int u = muchii[i].a, v = muchii[i].b, cost = muchii[i].k;
        /// 1. nu au mai fost folosite
        if(comp[u].status == false && comp[v].status == false){
            comp[u].cmp = comp[v].cmp;
            comp[u].status = true; comp[v].status = true;
            rez.push_back(u); rez.push_back(v);
            graf[u].push_back(v); graf[v].push_back(u);
            sum += cost;
            ++nr_muchii;
            continue;
        }
        /// 2. e folosit doar un nod
        if(comp[u].status == true && comp[v].status == false){
            u1_v0(u, v);
            rez.push_back(u); rez.push_back(v);
            graf[u].push_back(v); graf[v].push_back(u);
            sum += cost;
            ++nr_muchii;
            continue;
        }
        if(comp[u].status == false && comp[v].status == true){
            u1_v0(v, u);
            rez.push_back(u); rez.push_back(v);
            graf[u].push_back(v); graf[v].push_back(u);
            sum += cost;
            ++nr_muchii;
            continue;
        }

        /// 3. sunt ambele folosite
        if(comp[u].status == true && comp[v].status == true){
            if(comp[u].cmp != comp[v].cmp){
                u1_v1_dfs(v, comp[u].cmp);
                rez.push_back(u); rez.push_back(v);
                graf[u].push_back(v); graf[v].push_back(u);
                sum += cost;
                ++nr_muchii;
                continue;
            }
        }
    }
    out<<sum<<'\n'<<nr_muchii<<'\n';
    for(int i = 0; i < rez.size(); i+=2)
        out << rez[i] << ' ' << rez[i+1] << '\n';

    in.close();
    out.close();
    return 0;
}