#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct Edge
{
    int u, v, cost;
};

vector<int> parent, ranks;
bool comp(Edge a, Edge b)
{
    return a.cost < b.cost;
}
int find(int nod)
{
    if(parent[nod] != nod)
        parent[nod] = find(parent[nod]);
    return parent[nod];
}
void unite(int x, int y)
{
    int fx = find(x);
    int fy = find(y);
    if(ranks[fx] < ranks[fy])
        parent[fx] = fy;
    else
    {
        parent[fy] = fx;
        if(ranks[fx] == ranks[fy]) ranks[fx]++;
    }

}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;

    fin >> N >> M;
    ranks.resize(N + 1);
    parent.resize(N + 1);
    vector<Edge> edges(M);
    for(int i = 1; i <= N; i++)
        parent[i] = i;
    for(int i = 0; i < M; i++)
        fin >> edges[i].u >> edges[i].v >> edges[i].cost;

    sort(edges.begin(), edges.end(), comp);
    long long total = 0;

    vector<pair<int,int>> sol;
    for(auto &e : edges)
    {
        if(find(e.u) != find(e.v))
        {
            unite(e.u, e.v);
            total += e.cost;
            sol.push_back({e.u, e.v});
        }
    }
    fout << total << '\n';
    fout << sol.size() << '\n';
    for(auto &p : sol)
        fout << p.first << ' ' << p.second << '\n';

    return 0;
}