#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e6;
const int INF = 1e8 ;

int father[MAXN], sizee[MAXN];

vector <pair <int, pair< int, int >>> g;
vector <pair <int, int>> ans;

int cmp(pair<int, int> a, pair <int, int> b){
    return a.second < b.second;
}

int findd(int nod1){
    if(father[nod1] == nod1) return nod1;
    return father[nod1] = findd(father[nod1]);
}

void unionn(int nod1, int nod2){

    int a = findd(nod1), b = findd(nod2);
    if(sizee[a] > sizee[b]) swap(a, b);

    father[a] = b;
    sizee[b] += sizee[a];
}

int main()
{
    int n, m, cnt = 0; fin >> n >> m;
    long long costf = 0;
    for(int i = 1; i <= m; ++i){
        int x, y, cost;
        fin >> x >> y >> cost;

        g.push_back({cost, {x, y}});
    }
    for(int i = 1; i <= n; ++i) father[i] = i, sizee[i] = 1;
    sort(g.begin(), g.end());

    for(auto x: g){
        int n1 = x.second.first;
        int n2 = x.second.second;
        int cost = x.first;

        if(findd(n1) != findd(n2)){
            costf += cost;
            cnt++;
            unionn(n1, n2);
            ans.push_back({n1, n2});
        }
    }
    fout << costf << '\n' << cnt << '\n' ;
    for(auto x: ans){
        fout << x.first << ' ' << x.second << '\n';
    }
    return 0;
}