#include <cstdio>
#include <algorithm>
#include <vector>
#define N 400010
using namespace std;

struct nod{
    int x,y,c;
}G[N];

int n,m,suma;
int GR[N];
vector <int> ind;

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

bool cmp(nod i,nod j)
{
    return (i.c<j.c);
}

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

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    for (int i=1;i<=n;i++)
        GR[i]=i;
    sort(G+1,G+m+1,cmp);
    int nr=0;
    for (int i=1;i<=m && nr<=n-1;i++)
        if(grupa(G[i].x)!=grupa(G[i].y))
        {
            suma+=G[i].c;
            ind.push_back(i);
            GR[grupa(G[i].x)]=grupa(G[i].y);
            nr++;
        }
    printf("%d\n%d\n",suma,n-1);
    for (int i=0;i<n-1;i++)
        printf("%d %d\n",G[ind[i]].x,G[ind[i]].y);
    return 0;
}