#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int n,m,i,pmin,nr,ct,aux,s[200001];
struct muchie{int x,y,c;};
struct csort
{
    bool operator()(muchie a,muchie b)
    {
        return a.c>b.c;
    }
};
priority_queue<muchie,vector<muchie>,csort> q;
vector<muchie> a[200001],sol;
muchie auxm;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%ld %ld",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%ld %ld %ld",&auxm.x,&auxm.y,&auxm.c);
        a[auxm.x].push_back(auxm);
        aux=auxm.x;
        auxm.x=auxm.y;
        auxm.y=aux;
        a[auxm.x].push_back(auxm);
    }
    s[1]=1;
    pmin=1;
    while(nr<n-1)
    {
        for(i=0;i<a[pmin].size();i++)
        {
            if(s[a[pmin][i].y]==0)
            q.push(a[pmin][i]);
        }
        while(s[q.top().y]==1) q.pop();
        auxm=q.top();
        sol.push_back(auxm);
        ct+=auxm.c;
        pmin=auxm.y;
        s[auxm.y]=1;
        nr++;
    }
    printf("%ld\n%ld\n",ct,n-1);
    for(i=0;i<sol.size();i++)
        printf("%ld %ld\n",sol[i].x,sol[i].y);
}