#include<fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct afisare{int x;int y;};
afisare v[200000];
int a[1501][1501],c[1501][1501],nodul[200000];
bool viz[1501];
int main()
{
    int n,m,x,y,cost,i,min,suma=0,j,nr_de_muchii=0,q=1;
    f>>n>>m;
    //Am citit drumurile si costurile.
    while(m>0)
    {
        f>>x>>y;
        a[x][y]=a[y][x]=1;
        f>>cost;
        c[x][y]=c[y][x]=cost;
        m--;
    }
    //for(i=1;i<=n;i++){for(j=1;j<=n;j++)g<<c[i][j]<<" ";g<<endl;}

    int p=1,nod,nod_nou,nod_mama,l=1;
    nodul[p]=1;viz[p]=1;
    while(p<n)
    {
        min=100000;
        while(l<=p)
        {

            nod=nodul[l];//g<<"Se verifica nodul "<<nod<<endl;
            for(i=1;i<=n;i++)
                    if(a[nod][i]==1&&viz[i]==0)
                        if(c[nod][i]<min)
                        {
                            min=c[nod][i];
                            //g<<"minimul s-a schimbat cu "<<min<<endl;
                            nod_nou=i;
                            nod_mama=nod;
                        }
            l++;
        }
            suma+=min;//g<<"min este "<<min<<" //NOD ADAUGAT: "<<nod_nou<<endl;
            nr_de_muchii++;
            viz[nod_nou]=1;
            p++;nodul[p]=nod_nou;
            l=1;
            v[q].x=nod_nou;v[q].y=nod_mama;q++;
    }
    g<<suma<<endl<<nr_de_muchii<<endl;q--;
    for(i=1;i<=q;i++)g<<v[i].x<<" "<<v[i].y<<endl;
    return 0;
}