#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
FILE *fin = fopen("apm.in", "r");
FILE *fout = fopen("apm.out","w");
int tata[200000];

int finder(int x)
{
    if(tata[x]==x) return x;
    else
    {
        tata[x] = finder(tata[x]);
        return tata[x];
    }
}
void uniune(int x, int y)
{
    int j = finder(y);
    int i = finder(x);
    tata[i]=j;
}
struct con
{
    int a,b,cost;
};
con raspuns[200000];
bool sortare(con ab, con ba)
{
    if(ab.cost<ba.cost) return true;
    return false;
}
struct pereche
{
    int cost,nod;
};
char vazut[200000];
vector <pereche> muchie[200000];
con conexiuni[200000];
int main()
{
    int n,m;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        fscanf(fin,"%d%d%d", &x,&y,&z);
        conexiuni[i].a=x;
        conexiuni[i].b=y;
        conexiuni[i].cost=z;
        tata[x]=x;
        tata[y]=y;
       // muhche[y].push_back(pereche{x,z});
    }
    sort(conexiuni+1,conexiuni+m+1,sortare);
    int total=0;
    int ramas=1;
    for(int i=1;i<=m;i++)
    {
        if(finder(conexiuni[i].a)!=finder(conexiuni[i].b) )
        {
            vazut[conexiuni[i].b]=1;
            vazut[conexiuni[i].a]=1;
            total+=conexiuni[i].cost;
            uniune(conexiuni[i].a,conexiuni[i].b);
            raspuns[ramas].a=conexiuni[i].a;
            raspuns[ramas].b=conexiuni[i].b;
            ramas++;
        }
    }
    fprintf(fout,"%d\n%d\n",total,ramas-1);
    for(int i=1;i<ramas;i++)
    {
        fprintf(fout,"%d %d\n", raspuns[i].a,raspuns[i].b);
    }
    return 0;
}