#include <cstdio>
#include <vector>
#define DMAX 200010//maxim 200 000 de varfuri
#define INF 999999
using namespace std;

void citire(); void rez(); void afisare();
inline void selectare (int);

struct vecin{
    int vec;
    int cost;
};

vector <vecin> L[DMAX];
int n, m, cmin[DMAX], prec[DMAX], cost_APM;
bool Z[DMAX];

int main()
{
    citire();
    rez();
    afisare();
    return 0;
}

void citire()
{
    FILE*fin=fopen ("apm.in", "r");
    fscanf (fin, "%d %d", &n, &m);
    int i, x, y;
    struct vecin aux;
    for (i=1; i<=m; ++i)
    {
        fscanf (fin, "%d %d %d", &x, &y, &aux.cost);
        aux.vec=y;
        L[x].push_back(aux);
        aux.vec=x;
        L[y].push_back (aux);
    }
    fclose (fin);
}

void rez()
{
    //initializez solutia
    int i, vfmin, j, minim;

    Z[1]=1;
    for (i=2; i<=n; ++i)
    {
            prec[i]=1;
            cmin[i]=INF;
    }
    for (i=0; i<L[1].size(); ++i)
        cmin[L[1][i].vec]=L[1][i].cost;

    for (i=2; i<=n; ++i)
    {
        minim=INF;
        for (j=2; j<=n; ++j)
            if (!Z[j] && cmin[j]<minim)
        {
            minim=cmin[j];
            vfmin=j;
        }
        selectare (vfmin);
        cost_APM+=minim;
    }
    return;
}

inline void selectare (int vf)
{
    //il adaug pe vf in solutie
    int i;
    Z[vf]=1;
    for (i=0; i<L[vf].size(); ++i)
        if (cmin[L[vf][i].vec]>L[vf][i].cost && !Z[L[vf][i].vec])
        {
            cmin[L[vf][i].vec]=L[vf][i].cost;
            prec[L[vf][i].vec]=vf;
        }
    return;
}

void afisare()
{
    FILE*fout=fopen ("apm.out", "w");
    fprintf (fout, "%d %d\n", cost_APM, n-1);
    int i;
    for (i=2; i<=n; ++i)
        fprintf (fout, "%d %d\n", i, prec[i]);
    fclose (fout);
}