#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

struct Edge{
    int x, y, c;
    bool inTree = false;
};

Edge v[400005];

int n, m, id[200001], sz[200001];

int _find(int x){

    int root = x;
    while(root != id[root]) root = id[root];

    int next;
    while(x != root)
    {
        next = id[x];
        id[x] = root;
        x = next;
    }

    return root;
}

bool _union(int x, int y)
{
    int rootx = _find(x);
    int rooty = _find(y);

    if(rootx == rooty) return false;

    if(sz[rootx] > sz[rooty]){
        sz[rootx] += sz[rooty];
        id[rooty] = rootx;
    }
    else{
        sz[rooty] += sz[rootx];
        id[rootx] = rooty;
    }

    return true;
};


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

    fin >> n >> m;

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

    for(int i = 1; i <= n; ++i)
        id[i] = i, sz[i] = 0;

    sort(v + 1, v + m + 1, [](Edge A, Edge B){return A.c < B.c;});

    long long cost = 0;

    for(int i = 1; i <= m; ++i)
    {
        if(_union(v[i].x, v[i].y))
        {
            v[i].inTree = true;
            cost += v[i].c;
        }
    }


    fout << cost << '\n' << n - 1 << '\n';

    for(int i = 1; i <= m; ++i)
        if(v[i].inTree == true) fout << v[i].x << ' ' << v[i].y << '\n';


}