#include <fstream>
#include <vector>

#define IN "prim.in"
#define OUT "apm.out"

#define NMAX 200005
#define INF 2000000000

using namespace std;

struct Muchie
{
    int y, cost;
};

vector <Muchie> G[NMAX];
int n, m, cmin[NMAX], p[NMAX], M[NMAX];

void citire();
void Prim(int);
void afisare();
int c_minim(int, int);

int main()
{
    citire();
    Prim(1);
    afisare();
    return 0;
}

void citire()
{
    Muchie A;
    int i, x, y, c;
    FILE * fin = freopen(IN, "r", stdin);
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d", &x, &y, &c);
        A.y=x;
        A.cost=c;
        G[y].push_back(A);
        A.y=y;
        G[x].push_back(A);
    }
}

void Prim(int x)
{
    int i, j, minim, selectat, val;
    for(i=2;i<=n;++i)
    {
        cmin[i]=c_minim(x, i);
        p[i]=x;
    }
    M[x]=1;
    for(i=1;i<=n-1;++i)
    {
        minim=INF;
        for(j=1;j<=n;++j)
        {
            if(!M[j]&&cmin[j]<minim)
            {
                minim=cmin[j];
                selectat=j;
            }
        }
        M[selectat]=1;
        for(j=1;j<=n;++j)
        {
            if(M[j]&&j!=selectat)
                continue;
            val=c_minim(selectat, j);
            if(val<cmin[j])
            {
                cmin[j]=val;
                p[j]=selectat;
            }
        }
    }
}

int c_minim(int x, int y)
{
    int c_min=INF, i;
    for(i=0;i<G[x].size();++i)
    {
        if(G[x][i].y==y)
            if(G[x][i].cost<c_min)
                c_min=G[x][i].cost;
    }
    return c_min;
}

void afisare()
{
    int i, cost=0;
    FILE * fout = freopen(OUT, "w", stdout);
    for(i=2;i<=n;++i)
    {
        cost+=cmin[i];
    }
    printf("%d\n", cost);
    printf("%d\n", n-1);
    for(i=2;i<=n;++i)
    {
        printf("%d %d\n", i, p[i]);
    }
}