#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 L[a.first][a.second].c>L[b.first][b.second].c;
    }
};
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(nod , j));

}
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;
    nodd aux;
    pair < int , int > auxxx;
    preparare(1);
    int prec=1;
    viz[1]=true;
    while(!q.empty())
    {
        auxxx=q.top();
        aux=L[auxxx.first][auxxx.second];
        nodcur=aux.inf;
        q.pop();
        if(viz[nodcur])continue;
        tata[aux.inf]=auxxx.first;
        sol+=aux.c;
        viz[nodcur]=true;

        preparare(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;
}