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

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

const int MAX = 2e5 + 5;

int n, m, totalCost;
int father[MAX];
typedef pair<int, int> muchie;
vector<pair<int, muchie> > edges;
vector<muchie> answer;

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

void unite(int x, int y)
{
    x = dad(x);
    y = dad(y);
    father[y] = x;
}

void Read_Input()
{
    f >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        f >> x >> y >> c;
        edges.push_back({c, {x, y}});
    }
}

void APM()
{

    sort(edges.begin(), edges.end());
    for(int i = 1; i <= n; ++i)
        father[i] = i;
    for(int i = 0; i < edges.size(); ++i)
    {
        int x = edges[i].second.first;
        int y = edges[i].second.second;
        int cost = edges[i].first;

        if(dad(x) != dad(y))
        {
            totalCost += cost;
            unite(x, y);
            answer.push_back({x, y});
        }
    }
}

void Print_Output()
{
    g << totalCost << "\n" << answer.size() << "\n";
    for(int i = 0; i < answer.size(); ++i)
        g << answer[i].first << " " << answer[i].second << "\n";
}

int main()
{
    Read_Input();
    APM();
    Print_Output();
    return 0;
}