#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iomanip>

using namespace std;

#define ll long long

struct DSU {
    vector<int> parent, rank;

    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i; // each node is its own root
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // path compression
        return parent[x];
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false; // same set, cycle if edge added

        if (rank[a] < rank[b]) swap(a, b); // attach smaller under bigger
        parent[b] = a;
        if (rank[a] == rank[b]) rank[a]++;
        return true;
    }
};

int n, m;
vector<vector<pair<int, int>>> graph;
vector<pair<pair<int, int>, int>> edges;

void ReadData() {
    cin >> n >> m;

    graph.assign(n, vector<pair<int, int>>());

    for(int i = 0; i < m ; ++i){
        int start, end, cost;
        cin >> start >> end >> cost;
        start--; end--;
        edges.push_back({{start, end}, cost});
    }
    
}

bool comparator(const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b ){
    return a.second < b.second;
}


void Solve() {
    sort(edges.begin(), edges.end(), comparator);
    int index = 0;
    DSU dsu(n);

    vector<pair<pair<int, int>, int>> ed;

    while (index < edges.size()) {
        if (dsu.unite(edges[index].first.first,edges[index].first.second )){
            ed.push_back(edges[index]);
            int start = edges[index].first.first;
            int end = edges[index].first.second;
            int cost = edges[index].second;
            graph[start].push_back({end, cost});
            graph[end].push_back({start, cost});
        }
        index++;
    }
    int result = 0;

    for(pair<pair<int, int>, int> val : ed){
        result += val.second;
    }
    cout << result << "\n";
    cout << ed.size() << "\n";

    for(pair<pair<int, int>, int> val : ed){
        cout << val.first.first + 1 << " " << val.first.second + 1;
        cout << "\n";
    }
    cout << "\n";

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    int t = 1;
    // cin >> t; // Uncomment for multiple test cases
    while (t--) {
        ReadData();
        Solve();   
    }
    return 0;
}