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

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

struct graf
{
    int node1, node2, cost;  
};

const int NMAX = 2 * 1e5+5;
int n, m, sets[NMAX], parent[NMAX];
graf adj[NMAX], sol[NMAX];

inline bool comp(const graf &x, const graf &y)
{
    return x.cost < y.cost;
}

inline int Find(int x)
{
    if(parent[x] == x)
        return x;
    return parent[x] = Find(parent[x]);
}

inline void Union(int x, int y)
{
    if(x == y)
        return;
    if(x > y)
        swap(x, y);
    parent[y] = parent[x];
    sets[x]+=sets[y];
}

inline void solve()
{
    int cost_final = 0, k = 1;
    sort(adj + 1, adj + m + 1, comp);
    for(int i = 1; i <= m; ++ i)
        parent[i] = i, sets[i] = 1;
    for(int i = 1; i <= m; ++ i)
    {
        int x = adj[i].node1;
        int y = adj[i].node2;
        if(Find(x) != Find(y))
        {
            Union(Find(x), Find(y));
            cost_final+=adj[i].cost;
            sol[k++] = adj[i];
        }
    }
    fout << cost_final << '\n' << n - 1 << '\n';
    for(int i = 1; i < n ; ++ i)
        fout << sol[i].node2 << ' ' << sol[i].node1 << '\n';
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++ i)
        fin >> adj[i].node1 >> adj[i].node2 >> adj[i].cost;
    solve();
}