#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] = min(cost[x][y], c);
    }

    vector<pair<int, int>> dist(n + 1);
    vector<bool> vis(n + 1, 0);
    vis[1] = 1;
    for(int i = 1; i <= n; i ++)
        dist[i] = {cost[1][i], 1};
    vector<pair<int, int>> edges;
    int ans = 0;

    for(int i = 1; i < n; i ++) {
        pair<int, int> aux = {INF, INF};
        int a;
        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;
}