#include <iostream>
#include <fstream>
#include <algorithm>
#define dim 400004

using namespace std;

ifstream f ("apm.in");
ofstream g ("apm.out");

struct {
    int x,y,cost;
}v[dim];

pair < int,int > lista[dim];

int n , m , SORT[dim] , l[200002] , k , x, y , cost;

void read()
{
    f >> n >> m;

    for(int i = 1;i <= m;i++)
        f >> v[i].x >> v[i].y >> v[i].cost;
}

void initializareVectori()
{
    int i;
    for(i = 1;i <= m;i++)
        SORT[i] = i;
    for(i = 1;i <= n;i++)
        l[i] = i;
}

bool cmp(int a,int b)
{
    if(v[a].cost < v[b].cost)
        return true;
    return false;
}

int grupa(int x)
{
    if(l[x] == x)
        return x;
    l[x] = grupa(l[x]);
    return l[x];
}

void uneste(int x,int y)
{
    l[grupa(x)] = grupa(y);
}

int main()
{
    read();
    initializareVectori();
    sort(SORT + 1, SORT + m + 1,cmp);

    for(int i = 1;i <= m;i++)
    {
        x = v[SORT[i]].x;
        y = v[SORT[i]].y;

        if(grupa(x) != grupa(y))
        {
            cost += v[SORT[i]].cost;
            lista[++k] = make_pair(x,y);
            uneste(x , y);
        }
    }

    g << cost << '\n' << k << '\n';

    for(int i = 1;i <= k; i++)
        g << lista[i].first << " " << lista[i].second << '\n';
    return 0;
}