#include<cstdio>
#include<queue>
#include<algorithm>
#include<bitset>
#include<vector>
using namespace std;
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
const int M=1<<30;
struct nodd
{
    int inf,c;
};
vector<nodd>L[200001];
bitset<200001>viz;
int tata[200001],n,m,sol;

struct cmp
{
    bool operator() ( pair< int , int > a , pair < int , int > b)
    {
        return a.first>b.first;
    }
};
priority_queue< pair < int , int > , vector< pair < int , int > > , cmp > q;
void preparare(int nod)
{
    for(int j=0;j<L[nod].size();j++)
        if(viz[L[nod][j].inf]==0)
             q.push(make_pair(L[nod][j].c,L[nod][j].inf));

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

}
void apm()
{
    int nodcur;
    preparare(1);
    int prec=1;
    viz[1]=true;
    while(!q.empty())
    {
        while(viz[q.top().second]==true&&!q.empty())q.pop();
        if(!q.empty())
        {

        nodcur=q.top().second;
        tata[q.top().second]=prec;
        sol+=q.top().first;
        viz[nodcur]=true;
        q.pop();
        preparare(nodcur);
        prec=nodcur;
        }
    }
    afisare();
}
int main()
{
    int i,x,y,z;
    nodd aux;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&z);
        aux.inf=x;
        aux.c=z;
        L[y].push_back(aux);
        aux.inf=y;
        L[x].push_back(aux);
    }
    apm();

    return 0;
}