#include <bits/stdc++.h>
#define ll long long
#pragma GCC optimize ("O3")
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define pii pair <int, int>
#define sz(x) (int)(x).size()

using namespace std;

const ll INF = 1e18;
const int NMAX = 50000;

struct sigmas {
    int a, b, w;

    bool operator < (const sigmas& other) const {
        return w < other.w;
    }
};

struct dsu {
    vector <int> DSU;

    dsu (int n) {
        DSU.resize (n + 2);
        for (int i = 1; i <= n; i ++) DSU[i] = i;
    }

    int find (int x) {
        if (DSU[x] != x) return DSU[x] = find (DSU[x]);
        return x;
    }

    void merge (int x, int y) {
        if (find (x) == find (y)) return;
        DSU[find (x)] = find (y);
    }

    bool same (int x, int y) {
        return find (x) == find (y);
    }
};

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

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

    int n, m; cin >> n >> m;
    vector <sigmas> edges;
    for (int i = 1; i <= m; i ++) {
        int u, v, w; cin >> u >> v >> w;
        edges.pb ({u, v, w});
    }

    sort(edges.begin(), edges.end());

    dsu dsuu (n);

    vector<sigmas> ans;
    ll partial = 0;
    for (auto e : edges) {
        int &u = e.a;
        int &v = e.b;
        int &w = e.w;

        if (!dsuu.same(u, v)) {
            ans.pb(e);
            dsuu.merge (u, v);
            partial += w;
        }

        for (int i = 1; i <= n; i ++) {
            cout << dsuu.DSU[i] << " \n"[n == i];
        }
    }

    cout << partial << "\n";
    cout << ans.size() << "\n";

    for (auto [u, v, w] : ans) {
        cout << u << " " << v << "\n";
    }

    return 0;
}