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

bool numar(char a)
{
    if (a >= '0' && a <= '9')
        return 1;
    return 0;
}

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);
        char* sir = new char[50];
        fgets(sir,50,in);

        int nr(0), nr1(0);
        for (int j = 0 ; sir[j] ; j++)
        {
            if (nr == 0 && sir[j] >= '0' && sir[j] <= '9') a = a * 10 + sir[j] - '0';
            if (nr == 1 && sir[j] >= '0' && sir[j] <= '9') b = b * 10 + sir[j] - '0';
            if (nr == 2 && sir[j] >= '0' && sir[j] <= '9') c = c * 10 + sir[j] - '0';
            if (sir[j] == '-') nr1 = 1;
            if (sir[j] == ' ') nr++;
        }

        a--;
        b--;

        if (nr1 == 1) c = -c;

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

        delete[] sir;
    }

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