#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

//vector < pair < int, int > > a[400005];
struct elem
{
    int a,b,c;
}a[400005];

int n,m,i,c;
int rnk[200005],dad[200005];

inline bool cmp(const elem &a,const elem &b)
{
    return a.c<b.c;
}

int root (int nod)
{
    int nodinit = nod, p = dad[nod];

    while(p != nod)
    {
        nod = p;
        p = dad[nod];
    }

    dad[nodinit] = p;
    return p;
}

void join (int p, int q)
{
    p = root(p);
    q = root(q);
    if( rnk[p] > rnk[q] )
        dad[q] = p;
    else
        if ( rnk[p] > rnk[q] )
            dad[p] = q;
    else
        rnk[q]++, dad[p] = q;
}


int main()
{
    int x,y,cost=0,sol[2][200005],k=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a[i].a>>a[i].b>>a[i].c;
        //a[x].push_back({y,c});
        //a[y].push_back({x,c});
    }

    for(i=1;i<=n;i++)
        dad[i]=i;

    sort(a+1,a+m+1,cmp);

    for(i=1;i<=m;i++)
    {
        if(root(a[i].a)!=root(a[i].b))
        {
            join(a[i].a,a[i].b);
            k++;
            sol[0][k]=a[i].a;
            sol[1][k]=a[i].b;
            cost+=a[i].c;
        }
    }

    fout<<cost<<'\n'<<k<<'\n';

    for(i=1;i<=k;i++)
        fout<<sol[0][i]<<" "<<sol[1][i]<<'\n';

    return 0;
}