#include <iostream>
#include <vector>
#include <algorithm>
int parent[200001];
int rank[200001];
struct edge
{
    int from; 
    int to;
    int val;
};

bool cmp(edge a, edge b)
{
    return a.val < b.val;
}

int find_root(int a)
{
    if(parent[a] == a)
        return a;
    return parent[a] = find_root(parent[a]);
}

void union_sets(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);

    if(root_a != root_b)
    {
        if(rank[root_a] > rank[root_b])
        {
            parent[root_b] = root_a;
        }
        else if (rank[root_a] < rank[root_b])
        {
            parent[root_a] = root_b;   
        }
        else 
        {
            parent[root_b] = root_a;
            rank[root_a]++;
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, m;
    std::cin >> n >> m;
    std::vector<edge> muchii(m + 1);
    
    for(int i = 1; i <= m; i++)
    {
        int a, b, val;
        std::cin >> a >> b >> val;
        muchii[i] = {a, b, val};
    }
    std::sort(muchii.begin() + 1, muchii.begin() + m + 1, cmp);

    for(int i = 1; i <= n; i++)
    {
        parent[i] = i;
        rank[i] = 0;
    }   
    int cost = 0;
    std::vector<edge> arbore;
    for(int i = 1; i <= m; i++)
    {
        int a = muchii[i].from;
        int b = muchii[i].to;
        int val = muchii[i].val;

        if(find_root(a) != find_root(b))
        {
            union_sets(a, b);
            arbore.push_back({a, b, val});
            cost += val;
            ///std::cout << a << " " << b << "\n";
        }
    }
    std::cout << cost << "\n";
    std::cout << arbore.size() << "\n";
    for(edge a : arbore)
    {
        std::cout << a.from << " " << a.to << "\n";
    }
    return 0;
}