#include <bits/stdc++.h>
#define MAXN 400005

using namespace std;

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

int ind[MAXN], x[MAXN], y[MAXN], cost[MAXN], TT[MAXN], n, m, RG[MAXN];
vector <int> sol;
int s;

bool cmp(int a, int b)
{
    return (cost[a]<cost[b]);
}

int find(int x)
{
    int R=x, y;
    while (TT[R]!=R)
        R=TT[R];
    while (TT[x]!=x)
    {
        y=TT[x];
        TT[x]=R;
        x=y;
    }
    return R;
}

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

int main()
{
    in >> n >> m;
    for (int i=1; i<=n; i++)
        TT[i]=i, RG[i]=1;
    for (int i=1; i<=m; i++)
        ind[i]=i;
    for (int i=1; i<=m; i++)
        in >> x[i] >> y[i] >> cost[i];
    sort(ind+1,ind+1+m,cmp);
    for (int i=1; i<=m; i++)
    {
        int a=find(x[ind[i]]);
        int b=find(y[ind[i]]);
        if (a!=b)
        {
            s+=cost[ind[i]];
            sol.push_back(ind[i]);
            unite(a,b);
        }
    }
    out << s << '\n';
    out << n-1 << '\n';
    for (int i=0; i<n-1; i++)
        out << x[sol[i]] << " " << y[sol[i]] << '\n';
    return 0;
}