#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
#include <tuple>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int Find(int x, vector<int>& parent)
{
    if(x == parent[x])
        return x;
    else return parent[x] = Find(parent[x], parent);
}
void Union(int x, int y, vector<int>& parent, vector<int>& rank)
{
    int rootx = Find(x, parent);
    int rooty = Find(y, parent);

    if(rank[rootx] < rank[rooty])
        {
            parent[rootx] = rooty;
        }
    else if(rank[rootx] > rank[rooty])
            parent[rooty] = rootx;
         else 
         {
            parent[rootx] = rooty;
            rank[rooty]++;
         }
}
int main()
{
    int n, m;
    fin >> n >> m;
    vector<tuple<int, int, int>> edges(m+1);
    vector<tuple<int, int, int>> apm_edges;
    vector<int> parent(n+1);
    vector<int> rank(n+1);
    for(int i = 1; i <= m; i++)
        {
            int x, y, weight;
            fin >> x >> y >> weight;
            edges[i] = make_tuple(weight, x, y);
        }
    sort(edges.begin(), edges.end());
    for(int i = 1; i <= n; i++)
        {
            parent[i] = i;
            rank[i] = 1;
        }
    int added_edges = 0;
    int cost = 0;
    for(tuple<int,int,int>edge: edges)
    {

        if(Find(get<1>(edge), parent) != Find(get<2>(edge), parent))
            {
                cost += get<0>(edge);
                Union(get<1>(edge), get<2>(edge), parent, rank);
                added_edges++;
                apm_edges.push_back(edge);
                if(added_edges == n-1)
                    break;
            }
    }
    fout << cost << '\n' << added_edges << '\n';
    for(int i = 0; i < added_edges; i++)
        fout << get<1>(apm_edges[i]) << " " << get<2>(apm_edges[i]) << '\n';
}