#include <bits/stdc++.h>

using namespace std;

struct edge
{
    int x, y, c;
};

int n, m, sum;
vector <int> parent, height;
vector <edge> edges, sol;

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

void mergeSets(edge x)
{
    int a, b;
    a = findParent(x.x);
    b = findParent(x.y);
    if(a == b)
         return;
    sum += x.c;
    if(height[a] < height[b])
        swap(a, b);
    parent[b] = a;
    if(height[a] == height[b])
        height[a] ++;
    sol.push_back(x);
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    cin >> n >> m;
    parent.resize(n + 1);
    height.resize(n + 1, 1);
    for(int i = 1; i <= n; i ++)
        parent[i] = i;

    for(int i = 0; i < m; i ++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        edges.push_back({x, y, c});
    }

    sort(edges.begin(), edges.end(), [](const edge &a, const edge &b)
    {
        return a.c < b.c;
    });

    for(int i = 0; i < m; i ++)
    {
        mergeSets(edges[i]);
    }

    cout << sum << "\n" << n - 1 << "\n";
    for(edge x : sol)
        cout << x.x << " " << x.y << "\n";
    return 0;
}