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

using namespace std;

struct muchie
{
    int x, y, cost;
    bool operator<(const muchie &that) const
    {
        return cost < that.cost;
    }
};

const int nMax = 200005;
const int mMax = 400005;

int n, m;
muchie v[mMax];
int father[nMax];
vector<int> ans;
int ansCost;

void citire()
{
    ifstream in("apm.in");
    in >> n >> m;
    for(int i = 1; i <= m; ++i)
        in >> v[i].x >> v[i].y >> v[i].cost;
    in.close();
}

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

void rezolvare()
{
    for(int i = 1; i <= n; ++i)
        father[i] = i;
    sort(v + 1, v + m + 1);
    ans.reserve(n - 1);
    for(int i = 1; i <= m; ++i)
    {
        if(GetFather(v[i].x) != GetFather(v[i].y))
        {
            ans.push_back(i);
            ansCost += v[i].cost;
            father[father[v[i].y]] = v[i].x;
        }
    }
}

void afisare()
{
    ofstream out("apm.out");
    out << ansCost << "\n" << n-1 << "\n";
    for(auto i:ans)
        out << v[i].x << " " << v[i].y << "\n";
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}