#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct graf{
    int nod1;
    int nod2;
    int cost;
};

int n, m, nr, father[200002], height[200002];
vector <graf> graphs;
vector <graf> solutii;

bool compare(graf a, graf b)
{
    return (a.cost < b.cost);
}

int Radacina(int k)
{
    while(father[k])
        k = father[k];
    return k;
}

void reunite(int a, int b)
{
    if(height[a] > height[b])
        father[b] = a;
    else
    {
        father[a] = b;
        if(height[a] == height[b])
            height[a]++;
    }
}

int main()
{
    int a, i, b;
    graf var;
    fin >> n >> m;
    while(fin >> var.nod1 >> var.nod2 >> var.cost)
        graphs.push_back(var);
    sort(graphs.begin(), graphs.end(), compare);
    i = 0;
    while(i < m)
    {
        a = Radacina(graphs[i].nod1);
        b = Radacina(graphs[i].nod2);
        if(a != b || a*b == 0)
            solutii.push_back(graphs[i]), reunite(a, b);
        i++;
    }
    a = solutii.size();
    for(i = 0; i < a; i++)
        nr+=solutii[i].cost;
    fout << nr << '\n';
    fout << a << '\n';
    for(i = 0; i < a; i++)
        fout << solutii[i].nod1 << " " << solutii[i].nod2 << '\n';

    return 0;
}