#include<cstdio>
#include<algorithm>
#include<vector>
#define pb push_back
#define nmax 400100

using namespace std;

int gr[nmax], x[nmax], y[nmax], c[nmax];
int n, m, ans, ind[nmax];

vector<int> g;

int grupa(int i)
{
    if (gr[i] == i) return i;
    gr[i] = grupa(gr[i]);
    return gr[i];
}

void reuniune(int i,int j)
{
    gr[grupa(i)] = grupa(j);
}

bool cmp(int i,int j)
{
    return(c[i]<c[j]);
}

int main()
{
    freopen("apm.in", "rt", stdin);
    freopen("apm.out", "wt", stdout);

    scanf("%d %d", &n, &m);

    for(int i=1; i<=m; ++i)
    {
        scanf("%d %d %d\n", &x[i], &y[i], &c[i]);
        ind[i]=i;
    }

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

    sort(ind+1, ind+m+1, cmp);
    for(int i=1; i<=m; ++i)
    {
        if (grupa(x[ind[i]])!=grupa(y[ind[i]]))
        {
            ans+=c[ind[i]];
            reuniune(x[ind[i]], y[ind[i]]);
            g.pb(ind[i]);
        }
    }

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

    printf("%d\n", n-1);
    for(int i=0; i<n-1; ++i)
    printf("%d %d\n", x[g[i]], y[g[i]]);

    return 0;
}