#include <cstdio>
#include <algorithm>
#include <vector>
#define Nmax 400005
using namespace std;

FILE *fin=freopen("apm.in","r",stdin);
FILE *fout=freopen("apm.out","w",stdout);

int n,m,gr[Nmax],s;

struct muchie
{
    int x;
    int y;
    int c;
}g[Nmax];

bool cmp(muchie a, muchie b)
{
    if(a.c>b.c)
        return false;
    return true;
}

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

void citire()
{
    scanf("%d %d",&n,&m);
    int a,b,c;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&g[i].x,&g[i].y,&g[i].c);
    }
}

vector <int> ind;

int main()
{
    citire();
    for(int i=1;i<=m;i++)
        gr[i]=i;
    sort(g+1,g+m+1,cmp);
    int nr=0;
    for(int i=0;i<m && nr<=n-1;i++)
        if(grupa(g[i].x)!=grupa(g[i].y))
        {
            s+=g[i].c;
            ind.push_back(i);
            gr[grupa(g[i].x)]=grupa(g[i].y);
            nr++;
        }
    printf("%d\n%d\n",s,n-1);
    for (int i=0;i<n-1;i++)
        printf("%d %d\n",g[ind[i]].x,g[ind[i]].y);
    return 0;
}