#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 200000+5

using namespace std;

struct m
{
    int x,y,c;
} leg[NMAX*2];
int N,M;
int p[NMAX];
vector<m> apm;

bool cmp(m a,m b)
{
    return a.c<b.c;
}

int _find(int i)
{
    if(p[i]==i)return i;
    p[i]=_find(p[i]);
    return p[i];
}

int _merge(int x,int y)
{
    p[_find(x)]=_find(y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int ans=0;
    scanf("%d %d",&N,&M);
    for(int i=1; i<=M; i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        m l;
        l.x=x;
        l.y=y;
        l.c=z;
        leg[i]=l;
    }
    sort(leg+1,leg+M+1,cmp);

    for(int i=1;i<=N;i++)
        p[i]=i;

    for(int i=1;i<=M;i++)
    {
        int x=leg[i].x;
        int y=leg[i].y;
        int c=leg[i].c;
        if(_find(x)!=_find(y))
        {
            ans+=c;
            _merge(x,y);
            apm.push_back(leg[i]);
        }
    }

    printf("%d\n",ans);

    printf("%d\n",apm.size());

    for(int i=0;i<apm.size();i++)
        printf("%d %d\n",apm[i].x,apm[i].y);

    return 0;
}