#include <fstream>
#include <queue>
#include <functional>
#define NMAX 200004
#define MMAX 400004
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct muchie
{
    int x, y, c;
    friend bool operator> (muchie a, muchie b);
};
bool operator> (muchie a, muchie b)
{
    return a.c > b.c;
}

priority_queue<muchie, vector<muchie>, greater<muchie> > H;  //H e max_heap nu min_heap
vector <muchie> A; // apm
int cmin; // costul apm-ului

int n, m;
int tata[NMAX];
int h[NMAX];

int Find(int x)
{
    int y;
    int rad = x;
    while(tata[rad] != 0)
        rad = tata[rad];
    // compresia drumului
    if(rad != x)
    {
        y = tata[x];

        while(y != rad)
        {
            tata[x] = rad;
            x = y;
            y = tata[x];
        }
    }
    return rad;
}

void Union(int x, int y)
{
    int i=Find(x);
    int j=Find(y);

    if(i != j)
    {
        if(h[i] < h[j])
        {
            tata[i] = j;
        }
        else
        if(h[j] > h[i])
        {
            tata[j] = i;
        }
        else
        {
            tata[i] = j;
            h[j]++;
        }
    }
}

void citire();
void kruskal();
void afisare();

int main()
{
    citire();
    kruskal();
    afisare();
}

void citire()
{
    muchie aux;
    cin >> n >> m;
    for(int i=0; i < m; i++)
    {
        cin >> aux.x >> aux.y >> aux.c;
        H.push(aux);
    }
}

void kruskal()
{
    muchie aux;
    int i, j;
    while(A.size() < n-1)
    {
        aux = H.top();
        H.pop();
        i = Find(aux.x);
        j = Find(aux.y);

        if(i != j)
        {
            A.push_back(aux);
            cmin += aux.c;
            Union(i, j);
        }
    }
}

void afisare()
{
    cout << cmin << '\n';
    cout << n-1 << '\n';
    for(int i=0; i < n-1; i++)
    {
        cout << A[i].x << ' ' << A[i].y << '\n';
    }
}