#include <cstdio>
#include <algorithm>
#include <vector>
#define filein "apm.in"
#define fileout "apm.out"
using namespace std;

struct muc
{
    int x;
    int y;
    int c;
};

int N,M;
int Sum;
muc m[400001];
int ind[400001];
int gr[400001];

vector <int> muchii;

void ReadData();
void PrintData();

int Group(int a);
bool Cmp(int x, int y);
void Reunion(int a, int b);

int main()
{
    ReadData();
    sort(ind+1,ind+M+1,Cmp);
    register int i;
    for (i=1; i<=M; i++)
        if (Group(m[ind[i]].x)!=Group(m[ind[i]].y))
        {
            Sum+=m[ind[i]].c;
            Reunion(m[ind[i]].x,m[ind[i]].y);
            muchii.push_back(ind[i]);
        }
    PrintData();
    return 0;
}

void ReadData()
{
    FILE *in;
    in=fopen(filein,"r");
    fscanf(in,"%d%d",&N,&M);
    register int i;
    for (i=1; i<=M; i++)
    {
        fscanf(in,"%d%d%d",&m[i].x,&m[i].y,&m[i].c);
        ind[i]=i;
    }
    for (i=1; i<=N; i++)
        gr[i]=i;
    fclose(in);
}

void PrintData()
{
    FILE *out;
    out=fopen(fileout,"w");
    vector <int> :: iterator it;
    fprintf(out,"%d\n",Sum);
    fprintf(out,"%d\n",N-1);
    for (it=muchii.begin(); it<muchii.end(); it++)
        fprintf(out,"%d %d\n",m[(*it)].x,m[(*it)].y);
    fclose(out);
}

int Group(int a)
{
    if (gr[a]==a) return a;
    gr[a]=Group(gr[a]);
    return gr[a];
}

void Reunion(int a, int b)
{
    gr[Group(a)]=Group(b);
}

bool Cmp(int x, int y)
{
    return m[x].c<m[y].c;
}