#include <bits/stdc++.h>

#define nax 400005

using namespace std;

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

struct edge
{
    int x, y, cost;
};

vector<edge> graf;
vector<pair<int, int>> p;
vector<int> parents, rang;
int n, m, cost;

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

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

    sort(graf.begin()+1, graf.end(), [&](edge e1, edge e2){return e1.cost < e2.cost;});

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

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

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

void DoStuff()
{
    for(int i = 1; i <= m; ++i)
    {
        int parentX = Find(graf[i].x);
        int parentY = Find(graf[i].y);
        if(parentX != parentY)
        {
            Union(parentX, parentY);
            p.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 : p)
        g << it.first << " " << it.second << "\n";
}

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