#include <fstream>
#include <vector>
#define NMAX 100000
#define inf 0x3f3f3f3f

using namespace std;
struct muchie{
    int x;
    int c;
};
vector <muchie> G[NMAX];
ifstream fin ("apm.in");
ofstream fout("apm.out");
bool uz[NMAX];
int pre[NMAX];
int cmin[NMAX];

int n,m,cost,nrsel;
void citire();
void apm();
void afisare();
int main()
{
    citire();
    apm();
    afisare();
    return 0;
}

void citire()
{
    int i,j,c;
    fin>>n>>m;
    for(int k=0;k<m;k++)
    {
        muchie aux;
        fin>>i>>j>>c;
        aux.x=j;
        aux.c=c;
        G[i].push_back(aux);
        aux.x=i;
        G[j].push_back(aux);
    }
}

void apm()
{
    int vf,minim;
    ///initializari pentru vf de start
    uz[1]=1;
    pre[1]=0;
    cmin[1]=inf;
    ///             pentru celelalte varfuri
    for(int i=2;i<=n;i++)
    {
        pre[i]=1;
        cmin[i]=inf;
    }
    /// vizitez vecinii varfului de start
    for(int i=0;i<G[1].size();i++)
    {
        cmin[G[1][i].x]=G[1][i].c;
    }
    for(int k=0;k<n-1;k++)
    {
        minim=inf;
        for(int i=1;i<=n;i++)
        {
            if(uz[i]==0 && cmin[i]<minim)
            {
                minim=cmin[i];
                vf=i;
            }
        }
        uz[vf]=1;
        cost=cost+minim;

        for(int i=0;i<G[vf].size();i++)
        {
            if(uz[G[vf][i].x]==0 && cmin[G[vf][i].x]>G[vf][i].c)
            {
                cmin[G[vf][i].x]=G[vf][i].c;
                pre[G[vf][i].x]=vf;
                nrsel++;
            }
        }
    }
}

void afisare()
{
    fout<<cost<<'\n';
    fout<<nrsel<<'\n';
    for(int i=2;i<=n;i++)
    {
        fout<<i<<' '<<pre[i]<<'\n';
    }
}