#include <bits/stdc++.h>
#define tp tuple<int,int,int>
#define pr pair<int,int>
using namespace std;

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

int n, m, x, y, c, cost;
const int Max = 2e5 + 1;
vector<tp> edges;
vector<pr> mst;
vector<int> parent(Max, -1), d(Max, 1);

int find_set(int x)
{
    if(parent[x] == -1)
        return x;
    return parent[x] = find_set(parent[x]);
}

void union_sets(int x, int y)
{
    x = find_set(x);
    y = find_set(y);
    if(x == y)
        return;
    if(d[x] < d[y])
        swap(x, y);
    parent[y] = x;
    d[x] += d[y];
}

bool compare(tp x, tp y)
{
    return get<2>(x) < get<2>(y);
}

void kruskal()
{
    sort(edges.begin(), edges.end(), compare);
    for(auto i: edges)
    {
        tie(x, y, c) = i;
        if(find_set(x) != find_set(y))
        {
            union_sets(x, y);
            mst.push_back({x, y});
            cost += c;
        }
    }
    fout << cost << "\n" << n - 1 << "\n";
    for(auto i: mst)
        fout << i.first << " " << i.second << "\n";
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> c;
        edges.push_back({x, y, c});
    }
    kruskal();

    fin.close();
    fout.close();
    return 0;
}