#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define MAX 400005
#define NMAX 200005
int n, m, x, y, c, ans, muchii;
int tata[NMAX], com[NMAX];
struct noduri {
    int x, y, c;
}a[MAX];
vector<pair<int,int> > G;

bool comp(noduri a, noduri b)
{
    return a.c < b.c;
}

int root(int nod)
{
    int r = nod, y = nod, aux;
    while(tata[r])
        r = tata[r];
    
    while(y != r)
    {
        aux = tata[y];
        tata[y] = r;
        y = aux;
    }

    return r;
}

void unite(int x, int y)
{
    if (com[x] > com[y]){
        tata[y] = x;
    }else{
        tata[x] = y;
        if (com[x] == com[y])
            com[y] ++;
    }
}

int main()
{
    memset(com, 1, sizeof(com));
    fin >> n >> m;

    for (int i=1;i<=m;i++){
        fin >> a[i].x >> a[i].y >> a[i].c;
    }

    sort(a+1, a+m+1, comp);
    for (int i=1;i<=m;i++){
        int nod1 = root(a[i].x);
        int nod2 = root(a[i].y);
        if (nod1 != nod2){
            unite(nod1, nod2);
            muchii ++;
            ans += a[i].c;
            G.push_back({a[i].x, a[i].y});
        }
    }

    fout << ans << '\n' << muchii << '\n';
    for (auto it : G){
        fout << it.first << ' ' << it.second << '\n';
    }
    return 0;
}