#include <cstdio>
#include <utility>
#include <vector>

using namespace std;

vector<pair<int, int> > M[2010], sol;
int n,m,i,j,x,y,z,t[200010],A[200010],B[200010],cost;

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

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

    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        M[z+1000].push_back(make_pair(x,y));
    }
    for(i=1;i<=n;i++)
        t[i] = i;
    for(z=-1000;z<=1000;z++)
        for(auto it:M[z+1000])
        {
            x = it.first;
            y = it.second;
            A[1] = x; i = 1;
            B[1] = y; j = 1;
            while(x-t[x])
            {
                x = t[x];
                A[++i] = x;
            }
            while(y-t[y])
            {
                y = t[y];
                B[++j] = y;
            }
            if(x != y)
            {
                sol.push_back(it);
                cost += z;
                x = y;
            }
            for(;i;i--)t[A[i]] = x;
            for(;j;j--)t[B[j]] = y;
        }
    printf("%d\n",cost);
    printf("%d\n",n-1);
    for(auto it:sol)
        printf("%d %d\n",it.first,it.second);

    return 0;
}