#include <bits/stdc++.h>

using namespace std;

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

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

vector<muchie> graf;
vector<pair<int, int>> sol;
vector<int> tata, rang;
int n, m, cost;

void Read()
{
    f >> n >> m;
    graf.resize(m+1);
    tata.resize(n+1);
    rang.resize(n+1);

    for(int i = 1; i <= m; ++i)
        f >> graf[i].x >> graf[i].y >> graf[i].cost;

    sort(graf.begin()+1, graf.end());

    for(int i = 1; i <= n; ++i)
    {
        tata[i] = i;
        rang[i] = 1;
    }
}

int Find(int node)
{
    while(node != tata[node])
        node = tata[node];
    return node;
}

void Union(int x, int y)
{
    if(x == y)
        return;
    if(rang[x] < rang[y])
        tata[x] = y;
    else
        tata[y] = x;
    if(rang[x] == rang[y])
        ++rang[y];
}

void DoStuff()
{
    for(int i = 1; i <= m; ++i)
    {
        int tataX = Find(graf[i].x);
        int tataY = Find(graf[i].y);
        if(tataX != tataY)
        {
            Union(tataX, tataY);
            sol.push_back(make_pair(graf[i].x, graf[i].y));
            cost += graf[i].cost;
        }
    }
}

void Write()
{
    g << cost << "\n" << n - 1 << "\n";
    for(auto& it : sol)
        g << it.first << " " << it.second << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    Read();
    DoStuff();
    Write();
    return 0;
}