#include <bits/stdc++.h>
using namespace std;

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

// Determinare APM - Kruskal

typedef pair< int, int > iPair;

vector< vector< iPair > > G;
vector< pair< int, iPair > > edges;

int GetParent(int u, vector< int > &tata) {
    if(tata[u] == 0) {
        return u;
    }

    tata[u] = GetParent(tata[u], tata);
    return tata[u];
}

void Union(int u, int v, vector< int > &tata, vector< int > &h) {
    int uParent = GetParent(u, tata);
    int vParent = GetParent(v, tata);

    if(h[uParent] > h[vParent]) {
        tata[vParent] = uParent;
    } else {
        tata[uParent] = vParent;

        if(h[uParent] == h[vParent]) {
            h[vParent] = h[vParent] + 1;
        }
    }
}

vector< pair< int, iPair > > Kruskal(int n) {
    vector< int > tata(n), h(n);
    vector< pair< int, iPair > > apm;

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

    for(auto edge: edges) {
        int lhs = GetParent(edge.second.first, tata);
        int rhs = GetParent(edge.second.second, tata);

        if(lhs != rhs) {
            apm.push_back({edge.first, {lhs, rhs}});
            Union(lhs, rhs, tata, h);

            if((int)apm.size() == n - 1) {
                break;
            }
        }
    }

    return apm;
}

int main() {

    int n, m; in >> n >> m;
    G.resize(n);

    for(int i = 1; i <= m; ++i) {
        int x, y, cost; in >> x >> y >> cost;
        G[x - 1].push_back({y - 1, cost});
        G[y - 1].push_back({x - 1, cost});
        edges.push_back({cost, {x - 1, y - 1}});
    }

    vector< pair< int, pair< int, int > > > apm = Kruskal(n);

    if((int)apm.size() < n - 1) {
        cout << "Graful nu este conex\n";
    } else {
        int cost = 0;
        
        for(auto it: apm) {
            cost += it.first;
        }
        out << cost << "\n";

        out << (int)apm.size() << "\n";
        for(auto it: apm) {
            out << it.second.first + 1 << " " << it.second.second + 1 << "\n";
        }

        // cout << "Costul total este: " << cost << "\n";
    }

    return 0;
}