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

}
void afisare()
{
    for(int i=2;i<=n;i++)
        costapm+=cost[i];
    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;
}