#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector <pair<int, pair<int, int>>> edges;
int t[200005];

int get_root(int n)
{
    int aux = n;

    while(t[n] > 0)
        n = t[n];

    int root = n;
    n = aux;

    while(n != root)
    {
        aux = t[n];
        t[n] = root;
        n = aux;
    }
    return root;
}

bool join(int x, int y)
{
    int rootX = get_root(x);
    int rootY = get_root(y);
    if(rootX == rootY)
        return false;

    if(t[rootX] <= t[rootY])
    {
        t[rootX] += t[rootY];
        t[rootY] = rootX;
    }
    else
    {
        t[rootY] += t[rootX];
        t[rootX] = rootY;
    }
    return true;
}

int main()
{
    int i, n, m, a, b, c;
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        edges.push_back(make_pair(c, make_pair(a, b)));
    }
    sort(edges.begin(), edges.end());

    for(i = 1; i <= n; i++)
        t[i] = -1;

    vector<pair<int, int>> sol;
    int total = 0;
    for(i = 0; i < (int) edges.size(); i++)
    {

        if(join(edges[i].second.first, edges[i].second.second))
        {
            sol.push_back(make_pair(edges[i].second.first, edges[i].second.second));
            total += edges[i].first;
        }
    }

    printf("%d\n%d\n", total, (int) sol.size());
    for (i = 0; i < (int) sol.size(); ++i) {
        printf("%d %d\n", sol[i].first, sol[i].second);
    }
    return 0;
}