#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[100001],tata[100001],n,m,costapm,nod1,nod2;
bool viz[100001];
vector<nod>L[100001];
struct cmp
{
    bool operator()(coord a,coord b)
    {
        nod1=L[a.x][a.y].c;
        nod2=L[b.x][b.y].c;
        return nod1>nod2;
    }
};
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)
{
    coord aux;
    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])
            {
                aux.x=i;aux.y=j;
                cost[L[i][j].inf]=L[i][j].c;tata[L[i][j].inf]=i;
                heap.push(aux);
            }
}
void apm()
{
    int nodcur,i,j;
    for(int i=2;i<=n;i++)
        cost[i]=M;
    viz[1]=true;
    proceseaza(1);
    while(heap.size())
    {
        i=heap.top().x;j=heap.top().y;
        while(viz[L[i][j].inf]==true&&heap.size())
        {
            heap.pop();
            i=heap.top().x;j=heap.top().y;
        }
        if(heap.size())
        {
            nodcur=L[i][j].inf;
            costapm=costapm+L[i][j].c;
            heap.pop();
            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;
}