#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define Muchii_MAX 400005
#define Noduri_MAX 200005

using namespace std;

struct muchie
{
    int m1, m2, c;
} G[Muchii_MAX];

bool cmp(muchie a, muchie b)
{
    if(a.c<b.c)
        return 1;

    return 0;
}

int N, M, sum;
int GR[Noduri_MAX], rang[Noduri_MAX];
vector < pair < int, int > > rez;


void Read()
{
    scanf("%d%d", &N, &M);
    for(int i=1; i<=M; ++i)
    {
        scanf("%d%d%d", &G[i].m1, &G[i].m2, &G[i].c);
        GR[i]=i;
    }
}

int Find(int x)
{
    if(x!=GR[x])
        GR[x]=Find(GR[x]);

    return GR[x];
}

int Join(int x, int y)
{
    if(rang[x]>rang[y])
        GR[y]=x;
    else
        GR[x]=y;

    if(rang[x]==rang[y])
        rang[y]++;
}

void Solve()
{
    sort(G+1, G+M+1, cmp);
int sol=1;

    for(int i=1; sol<=N-1; ++i)
    {
        if(Find(G[i].m1)!=Find(G[i].m2))
        {
            sol++;
            sum+=G[i].c;
            Join(G[i].m1,G[i].m2);
            rez.push_back(make_pair(G[i].m1,G[i].m2));
        }
    }
}

void Print()
{
    cout<<sum<<"\n";
    cout<<N-1<<"\n";

    vector < pair < int, int > > ::iterator it;
    for(it=rez.begin(); it!=rez.end(); ++it)
        cout<<it->first<<" "<<it->second<<"\n";
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    Read();
    Solve();
    Print();
    return 0;
}