#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#define ll long long

using namespace std;

const int INF = 1e9 + 7;

int main() {

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

    int n, m;
    in >> n >> m;
    vector<vector<int>> cost(n + 1, vector<int> (n + 1, INF));
    for(int i = 1; i <= m; i ++) {
        int x, y, c;
        in >> x >> y >> c;
        cost[x][y] = cost[y][x] = c;
    }

    vector<pair<int, int>> dist(n + 1);
    vector<bool> vis(n + 1, 0);
    int ans = 0;
    int mn = INF, a = 1, b = 1;
    for(int i = 1; i <= n; i ++)
        for(int j = i + 1; j <= n; j ++)
            if(cost[i][j] < mn) {
                mn = cost[i][j];
                a = i;
                b = j;
            }
    ans += mn;
    vis[a] = vis[b] = 1;
    vector<pair<int, int>> edges;
    edges.push_back({a, b});
    for(int i = 1; i <= n; i ++)
        dist[i] = min(make_pair(cost[a][i], a), make_pair(cost[b][i], b));

    for(int i = 1; i < n - 1; i ++) {
        pair<int, int> aux = {INF, INF};
        for(int j = 1; j <= n; j ++) {
            if(!vis[j] && dist[j] < aux) {
                aux = dist[j];
                a = j;
            }
        }
        vis[a] = 1;
        edges.push_back({aux.second, a});
        ans += aux.first;

        for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], make_pair(cost[a][j], a));
    }

    out << ans << "\n" << edges.size() << "\n";
    for(auto it : edges)
        out << it.first << " " << it.second << "\n";

    return 0;
}