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

using namespace std;

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

struct d{
    int from, to, cost;
} drum[400005];

bool operator< (d a, d b)
{
    if (a.cost==b.cost)
    {
        return a.from<b.from;
    }
    return a.cost<b.cost;
}

int n, m, suma, father[200005], height[200005];

vector<d>sol;

int find(int x)
{
    if (father[x]==x)
    {
        return x;
    }
    father[x]=find(father[x]);
    return father[x];
}

void unire(int a, int b)
{
    a=find(a);
    b=find(b);
    father[b]=a;

}

void calculare()
{
    for (int i=1; i<=m; i++)
    {
        if (find(drum[i].from)==find(drum[i].to))
        {
            continue;
        }
        suma+=drum[i].cost;
        unire(drum[i].from,drum[i].to);
        sol.push_back(drum[i]);
    }
}

void initializare()
{
    for (int i=1; i<=n; i++)
        father[i]=i, height[i]=1;
}

int main() {
    f >> n >> m;
    initializare();
    for (int i=1; i<=m; i++)
    {
        f >> drum[i].from >> drum[i].to >> drum[i].cost;
    }
    sort(drum+1,drum+1+m);

    calculare();
    g << suma << '\n';
    g << n-1 << '\n';
    for (auto &v:sol)
    {
        g << v.to <<' ' <<v.from << '\n';
    }
    return 0;
}