#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

struct triplet
{
    int vf1, vf2, cost;

    bool operator() (triplet &a, triplet &b)
    {
        if (a.cost > b.cost)
            return 1;
        return 0;
    }
};

int find(int x, int* frate) // comprimare
{
    int r = x, y(0);
    while (r != frate[r])
        r = frate[r];
    while (x != frate[x])
    {
        y = frate[x];
        frate[x] = r;
        x = y;
    }
    return x;
}

void Kruskal_mlogn()
{
    FILE* in = fopen("apm.in","r");
    FILE* out = fopen("apm.out","w");
    int n(0), m(0);
    fscanf(in,"%d %d\n",&n,&m);

    priority_queue <triplet, vector<triplet>, triplet> PQ;

    for (int i = 0 ; i < m ; i++)
    {
        int a(0), b(0), c(0);
        fscanf(in,"%d %d %d\n",&a,&b,&c);
        a--;
        b--;

        triplet d = {a,b,c};
        PQ.push(d);
    }

    int* frate = new int[n];
    for (int i = 0 ; i < n ; i++)
        frate[i] = i;

    triplet* muchiiAlese = new triplet[n - 1];

    int componente(n), apcm(0);
    while (!PQ.empty() && (componente - 1))
    {
        triplet x = PQ.top();
        PQ.pop();

        int reprezentant1 = find(x.vf1,frate);
        int reprezentant2 = find(x.vf2,frate);
        if (reprezentant1 != reprezentant2)
        {
            apcm += x.cost;

            muchiiAlese[componente - 2] = {x.vf1,x.vf2,x.cost};

            frate[reprezentant1] = reprezentant2; // union
            componente--;
        }
    }
    fprintf(out,"%d\n%d\n",apcm,n - 1);
    for (int i = 0 ; i < n - 1 ; i++)
        fprintf(out,"%d %d\n",muchiiAlese[i].vf1 + 1,muchiiAlese[i].vf2 + 1);

    delete[] frate;
    fclose(in);
}

int main()
{
    Kruskal_mlogn();
    return 0;
}