#include <cstdio>
#include <queue>
#include <algorithm>
#define nMax 2000010
#define mMax 4000010

using namespace std;

struct muchii{
    int x;
    int y;
    int cost;
}a[mMax];

struct cmp{
    bool operator ()(const muchii &a, const muchii &b)const{
        return a.cost < b.cost;
    }
};

queue <int> afis;
int n;
int m;
int grupa[nMax];
int s;

int tati(int i)
{
    if (grupa[i] == i){
        return i;
    }
    return grupa[i] = tati(grupa[i]);
}

void reuniune(int i, int j)
{
   grupa[tati(i)] = tati(j);
}

void citire()
{
    scanf ("%d %d", &n, &m);
    for (int i = 0; i < m; ++ i){
        scanf ("%d %d %d", &a[i].x, &a[i].y, &a[i].cost);
    }
    for (int i = 1; i <= n; ++i){
        grupa[i] = i;
    }
    sort (a, a + m, cmp());
}

void kruskal()
{
    int N = -- n;
    for (int i = 0; n ; ++ i){
        if (tati(a[i].x) != tati(a[i].y)){
            reuniune(a[i].x, a[i].y);
            s += a[i].cost;
            afis.push(i);
            -- n;
        }
    }
    printf ("%d\n", s);
    printf ("%d\n", N);
    while (!afis.empty()){
        printf ("%d %d\n", a[afis.front()].x, a[afis.front()].y);
        afis.pop();
    }
}

int main()
{
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    citire();
    kruskal();

    return 0;
}