#include<stdio.h>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#define OVER9000 200001
#define orly 1005
using namespace std;

vector<int>a[2010];
int n,m,cmin,u,xt[OVER9000],yt[OVER9000],rad[OVER9000];

void read()
{
    assert(freopen("apm.in","r",stdin)!=NULL);
    int i,c,x,y;
    assert(scanf("%d%d",&n,&m)!=EOF);
    for(i=1;i<=m;++i)
    {
        assert(scanf("%d%d%d",&x,&y,&c)!=EOF);
        a[c+orly].push_back(x);
        a[c+orly].push_back(y);
    }
}

int tata(int k)
{
    if(rad[k]==k)
        return k;
    return rad[k]=tata(rad[k]);
}

void unite(int k,int l)
{
    int x=rand()%2;
    if(x==0)
        rad[rad[k]]=rad[l];
    else
        rad[rad[l]]=rad[k];
}

void solve()
{
    srand(time(0));
    int j,i;
    for(i=1;i<=n;i++)
        rad[i]=i;
    for(i=-1000;i<=1000;++i)
        for(j=0;j<a[i+orly].size();j+=2)
            if(tata(a[i+orly][j])!=tata(a[i+orly][j+1]))
            {
                cmin+=i;
                unite(a[i+orly][j],a[i+orly][j+1]);
                xt[++u]=a[i+orly][j];
                yt[u]=a[i+orly][j+1];
            }
}

void write()
{
    assert(freopen("apm.out","w",stdout)!=NULL);
    printf("%d\n%d\n",cmin,n-1);
    for(int i=1;i<=u;++i)
        printf("%d %d\n",xt[i],yt[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}