#include <fstream>
#include <algorithm>
#define NM 100000

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,i,P[NM],nrm[NM],k,p,q,j,T[NM],Rang[NM],cost,nr,sol[NM];

struct Edge
{
    int x,y,c;
    };
Edge E[100000];

bool cmp(Edge x, Edge y)
{
    return x.c<y.c;
    }

void unite(int x, int y)
{
    if(Rang[x]>Rang[y])
        T[y]=x;
    else
        T[x]=y;
    if(Rang[x]==Rang[y])
        Rang[y]++;
}

int check(int x)
{
    int R,z;
    for(R=x;T[R]!=R;R=T[R]);
        while(x!=T[x])
        {
            z=T[x];
            T[x]=R;
            x=z;
        }
    return R;
}

int main()
{
    f >> n >> m;
    for(i=1;i<=m;i++)
        f >> E[i].x >> E[i].y >> E[i].c;

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

    for(i=1; i<=n; i++)
    {
        T[i]=i;
        Rang[i]=1;
    }
    j=1; cost=0;
    while(nr < n-1)
    {
        while(check(E[j].x)==check(E[j].y))
        j++;
        nr++;
        sol[nr] = j;
        cost += E[j].c;
        unite(check(E[j].x), check(E[j].y));
    }

    g << cost << '\n';
    g << n-1 << '\n';
    for(i=1;i<n;i++)
        g << E[sol[i]].x << " " << E[sol[i]].y << '\n';

    f.close();
    g.close();

    return 0;
}

//70 de puncte
/*#include <fstream>
#include <algorithm>
#define NM 100000

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,i,P[NM],nrm[NM],k,p,q,j;

struct Edge
{
    int x,y,c;
    };
Edge E[100000];

bool cmp(Edge x, Edge y)
{
    return x.c<y.c;
    }

int main()
{
    f >> n >> m;
    for(i=1;i<=m;i++)
        f >> E[i].x >> E[i].y >> E[i].c;

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

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

    int cost=0;

    for(i=1;i<=m;i++)
        if(P[E[i].x]!=P[E[i].y])
        {
            k++;
            nrm[k]=i;
            cost+=E[i].c;
            p=P[E[i].x];
            q=P[E[i].y];
            for(j=1;j<=n;j++)
                if(P[j]==q) P[j]=p;
            if(k==n-1)
                break;
        }

    g << cost << '\n';
    g << k << '\n';

    for(i=1;i<=k;i++)
        g << E[nrm[i]].x << " " << E[nrm[i]].y << '\n';

    f.close();
    g.close();

    return 0;
}
*/