#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 200000;
const int MMAX = 400000;

struct muchii
{
    int x, y, z;
};

pair<int,int> tata[1 + NMAX];
muchii graf[1 + MMAX];
muchii raspuns[1 + MMAX];

bool comparare(muchii a, muchii b)
{
    return a.z < b.z;
}

int gasit(int a)
{
    if (tata[a].first == a)
    {
        return a;
    }
    else
    {
        tata[a].first = gasit(tata[a].first);
        return tata[a].first;
    }
}

void uneste(int a, int b)
{
    int x = gasit(a);
    int y = gasit(b);
    if (x == y)
    {
        return;
    }
    else
    {
        if (tata[x].second > tata[y].second)
        {
            tata[y].first = tata[x].first;
        }
        else if (tata[x].second < tata[y].second)
        {
            tata[x].first = tata[y].first;
        }
        else
        {
            tata[y].first = tata[x].first;
            tata[x].second++;
        }
    }
}

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        tata[i].first = i;
        tata[i].second = 1;
    }
    for (int i = 0; i < m; i++)
    {
        in >> graf[i].x >> graf[i].y >> graf[i].z;
    }
    sort(graf, graf + m, comparare);
    int sol = 0;
    int contor = 0;
    for (int i = 0; i < m; i++)
    {
        if(gasit(graf[i].x) != gasit(graf[i].y))
        {
            uneste(graf[i].x, graf[i].y);
            sol += graf[i].z;
            raspuns[contor]=graf[i];
            contor++;
        }
    }
    out << sol << '\n' << contor << '\n';
    for (int i = 0; i < contor; i++)
    {
        out << raspuns[i].x << ' ' << raspuns[i].y << '\n';
    }
    return 0;
}