#include <bits/stdc++.h>

using namespace std;

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

struct Edge
{
    int x, y;
    long long cost;
};

struct DSU
{
    vector<int> parent, sz;
    DSU(int n)
    {
        parent.resize(n+1);
        sz.resize(n+1, 1);
        for(int i = 1; i <= n; i++) parent[i] = i;
    }
    int find_set(int x)
    {
        if(parent[x] == x) return x;
        return parent[x] = find_set(parent[x]);
    }
    bool union_set(int a, int b)
    {
        a = find_set(a);
        b = find_set(b);
        if(a == b) return false;
        if(sz[a] < sz[b]) swap(a,b);
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

int main()
{
    int N, M;
    in >> N >> M;
    vector<Edge> edges(M);
    for(int i = 0; i < M; i++) in >> edges[i].x >> edges[i].y >> edges[i].cost;
    sort(edges.begin(), edges.end(), [](auto &a, auto &b)
    {
        return a.cost < b.cost;
    });
    DSU dsu(N);
    long long totalCost = 0;
    vector<pair<int,int>> ans;
    for(auto &e : edges)
    {
        if(dsu.union_set(e.x, e.y))
        {
            totalCost += e.cost;
            ans.push_back({e.x, e.y});
            if((int)ans.size() == N - 1) break;
        }
    }
    out << totalCost << "\n";
    out << ans.size() << "\n";
    for(auto &it : ans) out << it.first << " " << it.second << "\n";
    return 0;
}