#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;
}