#include <cstdio>
#include <vector>
#include <algorithm>
#define nmax 100000+5
#define mmax 500000+5
#define add push_back
using namespace std;

struct muchie
{
    int x, y;
    int cost;

    muchie(int x = 0, int y = 0, int cost = 0): x(x), y(y), cost(cost)
    {

    }
};

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

int tata[nmax];
vector<muchie> graf;
vector<muchie> apm;
int costAPM;

int stramos(int initial)
{
    int curent = initial;
    while (curent != tata[curent])
    {
        curent = tata[curent];
        tata[initial] = curent;
    }
    return curent;
}

bool conectat(int a, int b)
{
    return stramos(a) == stramos(b);
}

void conectare(int a, int b)
{
    tata[stramos(a)] = stramos(b);
}

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

    int k;
    muchie m;
    int n;
    int i;

    scanf("%d%d", &n, &k);

    for (i = 1; i <= k; i++)
    {
        scanf("%d%d%d", &m.x, &m.y, &m.cost);
        graf.add(m);
    }

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



    costAPM = 0;
    sort(graf.begin(), graf.end(), cmp);

    for (i = 0; i < graf.size(); i++)
        if (!conectat(graf[i].x, graf[i].y))
        {
            costAPM += graf[i].cost;
            conectare(graf[i].x, graf[i].y);
            apm.add(graf[i]);
        }

    printf("%d\n%d\n", costAPM, apm.size());
    for (i = 0; i < apm.size(); i++)
        printf("%d %d\n", apm[i].x, apm[i].y);
    return 0;
}