#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int N = 2e5 + 5, M = 4e5 + 5;
int sef[N];

struct edge{
    int x, y, c;
}muchii[M];

bool cmp(edge a, edge b){
    if(a.c > b.c)
        return 0;
    return 1;
}

int boss(int x){
    if(sef[x] == x)
        return x;
    return sef[x] = boss(sef[x]);
}

void unire(int x, int y){
    int sefx = boss(x);
    int sefy = boss(y);
    sef[sefx] = sefy;
}

bool verif(int x, int y){
    if(boss(x) == boss(y))
        return 1;
    return 0;
}

int main(){
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= m; i++){
        in >> muchii[i].x >> muchii[i].y >> muchii[i].c;
    }
    sort(muchii + 1, muchii + m + 1, cmp);

    for(int i = 1; i <= n; i++){
        sef[i] = i;
    }

    vector <int> ans;
    int cost = 0;
    for(int i = 1; i <= m; i++){
        int x = muchii[i].x, y = muchii[i].y, c = muchii[i].c;
        if(!verif(x, y)){
            unire(x, y);
            ans.push_back(i);
            cost += c;
            if(ans.size() == n - 1)
                break;
        }
    }

    out << cost << '\n' << n - 1 << '\n';
    for(auto it : ans)
        out << muchii[it].x << " " << muchii[it].y << '\n';
    return 0;
}