#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct mango
{
    int a, b, c;
}G[200005];

pair <int, int> sol[200005];
int n, m, sum, tata[200005], R[200005], nr;

bool Crit(mango x, mango y)
{
    return x.c < y.c;
}

void Unite(int x, int y)
{
    if(R[x] == R[y])
    {
        tata[y] = x;
        R[x]++;
    }
    else if(R[x] > R[y])
    {
        tata[y] = x;
    }
    else tata[x] = y;
}

int Tata(int nod)
{
    while(nod != tata[nod]) nod = tata[nod];
    return nod;
}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        f>>G[i].a>>G[i].b>>G[i].c;
    }
    for(int i = 1; i <= n; i++) tata[i] = i;
    sort(G+1,G+1+m,Crit);
    for(int i = 1; i <= m; i++)
    {
        if(Tata(G[i].a) != Tata(G[i].b))
        {
            Unite(Tata(G[i].a), Tata(G[i].b));
            sol[++nr] = make_pair(G[i].a, G[i].b);
            sum += G[i].c;
        }
    }
    g<<sum<<'\n';
    g<<nr<<'\n';
    for(int i = 1; i <= nr; i++) g<<sol[i].first<<' '<<sol[i].second<<'\n';
    return 0;
}