#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int lg=0;
struct statuie
{
    int x,y,r;
};
struct muchie
{
    int x,y;
} muc[200001];
bool crt(statuie x, statuie y)
{
    if(x.r!=y.r)
        return x.r<y.r;
    return x.x<y.x;
}
int cnt;
long long int sum;
statuie m[250001];
int p[100001];
int n,M,i;
int fynd(int x)
{
    int y,aux;
    y=x;
    while(y!=p[y])
    {
        y=p[y];
    }
    while(x!=p[x])
    {
        aux=p[x];
        x=p[x];
        x=aux;
    }
    return p[x];
}
void unite(int x,int y)
{
    int xx=fynd(x);
    int yy=fynd(y);
    p[yy]=p[xx];
}
int main()
{
    fin>>n>>M;
    for(i=1; i<=n; i++)
        p[i]=i;
    for(i=1; i<=M; i++)
    {
        int x,y,r;
        fin>>x>>y>>r;
        m[i].x=x;
        m[i].y=y;
        m[i].r=r;
    }
    sort(m+1,m+M+1,crt);
    /*for(i=1; i<=M; i++)
    {
        fout<<m[i].x<<" "<<m[i].y<<" "<<m[i].r<<'\n';
    }*/
    for(i=1; i<=M; i++)
    {
        if(fynd(m[i].x)!=fynd(m[i].y))
        {
            unite(m[i].x,m[i].y);
            muc[++lg].x=m[i].x;
            muc[lg].y=m[i].y;
            sum=sum+m[i].r;
            cnt++;
        }
        if(cnt==n-1)
        {
            fout<<sum<<'\n'<<n-1<<'\n';
            break;
        }
    }
    /*for(i=1; i<=n; i++)
    {
        fout<<p[i]<<" ";
    }*/
    for(i=1;i<=lg;i++)
        fout<<muc[i].y<<" "<<muc[i].x<<'\n';
    return 0;
}