#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#define MAXN 200005

using namespace std;
int t[MAXN], totalc, totalm;
priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater <pair<int, pair<int, int>>> > Q;
vector <pair<int, int> > sol;

int get_root(int x)
{
    int root = x, aux;
    while(t[root] > 0)
        root = t[root];

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

void join(int x, int y, int c)
{
    int rootX = get_root(x), rootY = get_root(y);

    if(rootX == rootY)
        return;

    totalc += c;
    totalm++;
    sol.push_back({x, y});

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

int main()
{
    int n, m, c, x, y;
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        t[i] = -1;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        Q.push({c, {x, y}});
    }
    while(!Q.empty())
    {
        x = Q.top().second.first;
        y = Q.top().second.second;
        c = Q.top().first;

        Q.pop();

        join(x, y, c);
    }
    printf("%d\n%d\n", totalc, totalm);
    for(int i = 0; i < sol.size(); i++)
    {
        printf("%d %d\n", sol[i].first, sol[i].second);
    }
    return 0;
}