#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;

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

const int maxn = 2e5  + 5;
const int oo = 1 << 29;
vector < pair<int,int> > G[maxn], Apm;
bitset <maxn> Vis;
int Dist[maxn], Dad[maxn];

class Heap_node {
public:
    int dad, node, cost;
    inline bool operator () (const Heap_node &X, const Heap_node &Y) {
        return X.cost > Y.cost;
    }
};

Heap_node Group(int x, int y, int z) {
    Heap_node aux;
    aux.dad = x;
    aux.node = y;
    aux.cost = z;
    return aux;
}

void Prim(int start, int n) {
    priority_queue <Heap_node, vector <Heap_node>, Heap_node> H;
    vector < pair<int,int> > :: iterator it;
    int dad, node, cost, i, minC = 0;
    for (i = 1; i <= n; i++) {
        Dist[i] = oo;
    }
    Dist[start] = 0;
    Dad[start] = 0;
    H.push(Group(0, start, 0));
    while (!H.empty()) {
        dad = H.top().dad;
        node = H.top().node;
        cost = H.top().cost;
        H.pop();
        if (node != start && Vis[node] == false) {
            minC += cost;
            Apm.push_back(make_pair(dad, node));
        }
        Vis[node] = true;
        for (it = G[node].begin(); it != G[node].end(); it++) {
            if (Vis[it->first] == false && Dist[it->first] > it->second) {
                Dist[it->first] = it->second;
                H.push(Group(node, it->first, it->second));
            }
        }
    }
    fout << minC << "\n" << n - 1 << "\n";
    for (it = Apm.begin(); it != Apm.end(); it++)  {
        fout << it->first << " " << it->second << "\n";
    }
}

int main() {
    ios_base :: sync_with_stdio (false);
    int n, m, x, y, c;
    fin >> n >> m;
    while (m--) {
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
        G[y].push_back(make_pair(x, c));
    }
    Prim(1, n);
    fin.close();
    fout.close();
    return 0;
}