#include <bits/stdc++.h>

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

//#define fin std::cin 
//#define fout std::cout 

const int NMAX = 1e5 + 5;

struct edge
{
    int x, y, cost;

    bool operator < (edge &other) const
    {
        return cost < other.cost;
    }
};

int n, m;
std::vector<edge> edges;
int father[NMAX], rang[NMAX];

std::vector<std::pair<int, int>> ans;
int MST_cost;

int Find(int node)
{
    if(father[node] != node)
        father[node] = Find(father[node]);
    return father[node];
}

void Union(edge __edge)
{
    int x = __edge.x;
    int y = __edge.y;
    int cost = __edge.cost;

    int fx = Find(x);
    int fy = Find(y);

    if(fx != fy) // daca sunt egale am forma un ciclu
    {
        MST_cost += cost;
        ans.push_back({x, y});

        if(rang[x] > rang[y])
            std::swap(rang[x], rang[y]);

        if(rang[x] == rang[y])
            rang[y]++;
        
        father[fx] = fy;
    }
}

int main() 
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        edge __edge;
        fin >> __edge.x >> __edge.y >> __edge.cost;
        edges.push_back(__edge);
    }

    // initializam DSU-ul
    for(int i = 1; i <= n; ++i)
        father[i] = i, rang[i] = 1;

    // sortam muchiile dupa cost
    std::sort(edges.begin(), edges.end());

    // unim muchia la MST (ne asiguram sa nu apara ciclu)
    for(auto __edge : edges)
        Union(__edge);

    
    fout << MST_cost << "\n" << ans.size() << "\n";
    for(auto pair : ans)
        fout << pair.first << " " << pair.second << "\n";

    return 0;
}