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

const int MAX = 200005;
int parent[MAX], rang[MAX];

struct Edge {
    int x, y, cost;
} a[400005];

bool cmp(Edge A, Edge B)
{
    return A.cost < B.cost;
}

int FindRoot(int node)
{
    if (parent[node] == node)
        return node;

    return parent[node] = FindRoot(parent[node]);
}

int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
        cin >> a[i].x >> a[i].y >> a[i].cost;

    for (int i = 1; i <= n; ++i)
        parent[i] = i;

    sort(a+1, a+m+1, cmp);

    int sum = 0;
    vector<pair<int,int>> path;
    for (int i = 1; i <= m; ++i)
    {
        int firstNode = FindRoot(a[i].x);
        int secondNode = FindRoot(a[i].y);
        if (firstNode != secondNode)
        {
            if (rang[firstNode] < rang[secondNode])
                swap(firstNode, secondNode);

            if (rang[firstNode] == rang[secondNode])
                ++rang[firstNode];

            path.push_back({a[i].y, a[i].x});
            sum += a[i].cost;
            parent[secondNode] = firstNode;
        }
    }

    cout << sum << "\n" << n-1 << "\n";
    for (auto x : path)
        cout << x.first << " " << x.second << "\n";

    return 0;
}