#include<cstdio>
#include<queue>
#include<vector>
#define M 2000000000
using namespace std;
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
struct nod
{
    int inf,c;
};
struct coord
{
    int x,y;
};
int cost[200001],tata[200001],n,m,costapm;
bool viz[200001];
coord auxx;
vector<nod>L[200001];
struct cmp
{
    bool operator()(coord a,coord b)
    {
        return L[a.x][a.y].c>L[b.x][b.y].c;
    }
};
priority_queue<coord,vector<coord>,cmp>heap;

void citire()
{
     nod aux;
    int x,y,z;
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&z);
        aux.c=z;
        aux.inf=y;L[x].push_back(aux);
        aux.inf=x;L[y].push_back(aux);
    }
}
void proceseaza(int i)
{

    for(int j=0;j<L[i].size();j++)
       if(viz[L[i][j].inf]==false)
            if(L[i][j].c<cost[L[i][j].inf])
            {
                auxx.x=i;auxx.y=j;
                cost[L[i][j].inf]=L[i][j].c;
                heap.push(auxx);
            }
}
void apm()
{
    int nodcur,i,j,k;
    for(i=2;i<=n;i++)
        cost[i]=M;
    viz[1]=true;
    proceseaza(1);
    for(k=1;k<n;k++)
    {

        while(viz[L[heap.top().x][heap.top().y].inf]==true)
        {
                heap.pop();
        }
            i=heap.top().x;j=heap.top().y;
            nodcur=L[i][j].inf;
            costapm=costapm+L[i][j].c;
            heap.pop();
            tata[L[i][j].inf]=i;
            viz[nodcur]=true;
            proceseaza(nodcur);
    }

}
void afisare()
{
    fprintf(g,"%d\n%d\n",costapm,n-1);
    for(int i=2;i<=n;i++)
        fprintf(g,"%d %d\n",i,tata[i]);

}
int main()
{
    citire();
    apm();
    afisare();
    return 0;
}