#include <fstream>
#include<algorithm>
#include <vector>
#define INF 100000000
using namespace std;
ifstream fin ("apm.in");
ofstream fout("apm.out");
struct muc {int vec,cost;}mu1,mu2;
vector <muc> G[400005];
int prec[200005],cmin[200005];
bool uz[200005];
void citire();
void rez();
bool comp (muc a,muc b);
int n,m;
int main()
{
    citire();
    rez();
    return 0;
}

void citire()
{
    int x,y,co;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>co;
        mu1.cost=co;
        mu1.vec=y;
        mu2.cost=co;
        mu2.vec=x;
        G[x].push_back(mu1);
        G[y].push_back(mu2);
    }

}

void rez ()
{
    int i,cn,costtot,mini,nod;
    for(i=2;i<=n;i++)
        {
         prec[i]=1;
         cmin[i]=INF;
        }
    uz[1]=1;
    for(i=0; i<G[1].size(); i++)
        if(cmin[G[1][i].vec] > G[1][i].cost)
        {
            cmin[G[1][i].vec]=G[1][i].cost;
            prec[G[1][i].vec]=1;
        }
    cn=n-1;
    costtot=0;
    while(cn)
    {
        cn--;
        mini=INF;
        for(i=1;i<=n;i++)
            if(!uz[i])
               if(cmin[i]<mini)
                {
                    mini=cmin[i];
                    nod=i;
                }
        uz[nod]=1;
        costtot+=mini;
        for(i=0; i<G[nod].size(); i++)
        if(cmin[G[nod][i].vec] > G[nod][i].cost)
        {
            cmin[G[nod][i].vec]=G[nod][i].cost;
            prec[G[nod][i].vec]=nod;
        }
    }
    fout<<costtot<<'\n';
    fout<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<i<<" "<<prec[i]<<'\n';
}