#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200005, MAXM = 400005;

struct muchie{
    int nod1, nod2, cost;
}edge[MAXM];

bool comp(muchie a, muchie b){
    return a.cost < b.cost;
}

int dad[MAXN], high[MAXN];
vector<pair<int, int> > ans;

int getroot(int nod){
    int root = nod;
    while(root != dad[root]) root = dad[root];
    while(nod != root){
        int cp = nod;
        nod = dad[nod];
        dad[cp] = root;
    }
    return nod;
}

void mergeset(int x, int y){
    int rx = getroot(x), ry = getroot(y);
    if(high[rx] > high[ry]) dad[ry] = rx;
    else if(high[rx] < high[ry]) dad[rx] = ry;
    else{
        dad[ry] = rx;
        high[rx]++;
    }
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
        fin >> edge[i].nod1 >> edge[i].nod2 >> edge[i].cost;
    for(int i = 1; i <= n; ++i){
        dad[i] = i;
        high[i] = 1;
    }
    sort(edge + 1, edge + m + 1, comp);
    int sum = 0;
    for(int i = 1; i <= m; ++i){
        int n1 = edge[i].nod1, n2 = edge[i].nod2;
        if(getroot(n1) == getroot(n2)) continue;
        else{
            sum += edge[i].cost;
            ans.push_back(make_pair(n1, n2));
            mergeset(n1, n2);
        }
    }
    fout << sum << "\n" << ans.size() << "\n";
    for(int i = 0; i < int(ans.size()); ++i)
        fout << ans[i].first << " " << ans[i].second << "\n";
    return 0;
}