#include <iostream>
#include <fstream>
#include <vector>
#define MMAX 400001
#define NMAX 200001
using namespace std;

ifstream fin ("apm.in");
ofstream fout("apm.out");

int n,m, t[NMAX], sol;

struct muchie
{
    int x,y,cost;
};

muchie muchii[MMAX], rez[NMAX];

int main()
{
    fin>>n>>m;
    
    for(int i = 0; i < m; i++)
        fin>>muchii[i].x>>muchii[i].y>>muchii[i].cost;

    int sch = 0;
    do
    {
        sch = 0;
        for(int i = 0; i < m - 1; i++)
        {
            if(muchii[i].cost > muchii[i + 1].cost)
            {
                swap(muchii[i], muchii[i + 1]);
                sch = 1;
            }
        }
    } while (sch);

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

    int suma = 0;
    for(int i = 0; i < m; i++)
        if(t[muchii[i].x] != t[muchii[i].y])
        {
            suma += muchii[i].cost;
            rez[sol] = muchii[i];
            sol++;
            int ai = t[muchii[i].x];
            int aj = t[muchii[i].y];
            for(int j = 1; j <= n; j++)
                if(t[j] == aj)
                    t[j] = ai;
        }

    fout<<suma<<'\n'<<sol<<'\n';
    for(int i = 0; i < sol; i++)
        fout<<rez[i].x<<' '<<rez[i].y<<'\n';

    return 0;
}