#include <iostream>
#include <fstream>
#include <cstring>
#define inf 30000
using namespace std;
int c[1501][1501];
int m,n,t[5001],d[5001],a[5001];
long ct;
bool u[5001];
void citeste()
{
    ifstream f("apm.in");
    f>>n>>m;
    memset(c,inf,sizeof(c));
    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        f>>c[x][y];
        c[y][x]=c[x][y];
    }
    f.close();
}
void prim(int x)
{
    int Min,nod;
    for(int i=1;i<=n;i++)
        d[i]=c[x][i], t[i]=x;
    u[x]=true;
    while(true)
    {
        Min=inf; nod=-1;
        for(int i=1;i<=n;i++)
            if(!u[i]&&Min>d[i])
                Min=d[i], nod=i;
        if(Min==inf) break;
        u[nod]=true;
        ct+=d[nod];
        a[nod]=t[nod];
        for(int i=1;i<=n;i++)
            if(d[i]>c[nod][i])
            {
                d[i]=c[nod][i];
                t[i]=nod;
            }
    }
}
void scrie()
{
    ofstream g("apm.out");
    g<<ct<<endl<<n-1<<endl;
    for(int i=1;i<=n;i++)
        if(a[i])g<<i<<" "<<a[i]<<endl;
    g.close();
}
int main()
{
    citeste();
    prim(5);
    scrie();
    return 0;
}