#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;
    }
};

struct pereche
{
    int vf, cost;
};

void Prim_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;

    vector<triplet>* muchii = new vector<triplet>[n];

    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--;

        muchii[a].push_back({a,b,c});
        muchii[b].push_back({b,a,c});
    }

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

    vector<triplet> muchiiAlese;

    int selectat(0), apcm(0);
    while (selectat != -1)
    {
        vizitat[selectat] = 1;

        int l = muchii[selectat].size();
        for (int i = 0 ; i < l ; i++)
            PQ.push(muchii[selectat][i]);

        selectat = -1;

        triplet x = PQ.top();
        PQ.pop();

        while (!PQ.empty() && vizitat[x.vf2] == 1)
        {
            x = PQ.top();
            PQ.pop();
        }

        if (vizitat[x.vf2] == 0)
        {
            selectat = x.vf2;
            muchiiAlese.push_back(x);
            apcm += x.cost;
        }
    }
    fprintf(out,"%d\n%d\n",apcm,n - 1);
    int l = muchiiAlese.size();
    for (int i = 0 ; i < l ; i++)
        fprintf(out,"%d %d\n",muchiiAlese[i].vf1 + 1,muchiiAlese[i].vf2 + 1);

    delete[] vizitat;
    fclose(in);
    fclose(out);
}

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