#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,cost=0,nr=0;
struct
{
    int x,y;
}af[801];
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;
        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];
                nr++;
                af[nr].x=t[nod];
                af[nr].y=nod;
                for (i=1;i<=n;i++)
                    if (d[i]>c[nod][i])
                        {
                            d[i]=c[nod][i];
                            t[i]=nod;
                        }


            }//cout<<cost;
    }
int main()
{
    int i;
    citire();
    prim (1);
    g<<cost<<'\n'<<nr<<'\n';
    for (i=1;i<=nr;i++)
        g<<af[i].x<<" "<<af[i].y<<'\n';

    return 0;
}