#include <iostream>
#include <fstream>
#define inf 1001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int t[801],d[801];
int c[801][801];
bool u[801];
int n,m;
void citire()
{
    int i,j,cost;
    f>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            c[i][j]=inf;
    for (i=1;i<=m;i++)
        {
            f>>i>>j>>cost;
            c[i][j]=cost;
            c[j][i]=cost;
        }

}
void prim (int x)
    {
        int i,min,nod,cost=0;
        for (i=1;i<=n;i++)
            {
                d[i]=c[x][i];
                t[i]=x;


            }
            u[x]=1;
        while (1)
            {
                min=inf;
                for (i=1;i<=n;i++)
                    if (!u[i] && d[i]<min)
                        {
                            min=d[i];
                            nod=i;
                        }
                if (min==inf) break;

                u[nod]=1;
                cost+=d[nod];
                cout<<t[nod]<<" "<<nod<<'\n';
                for (i=1;i<=n;i++)
                    if (d[i]>c[nod][i])
                        {
                            d[i]=c[nod][i];
                            t[i]=nod;
                        }


            }cout<<cost;
    }
int main()
{
    citire();
    prim (1);
    return 0;
}