#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const string fileName = "apm";
ifstream in  (fileName + ".in");
ofstream out (fileName + ".out");

const int maxSize = 100002;
const int inf = 0x3f3f3f3f;

priority_queue <pair <int , int>> primQue;
vector <pair <int , int>> adj[maxSize], toShow;
bitset <maxSize> visited;
int minCost[maxSize], parent[maxSize];

void prim(int startNode) {
    visited[startNode] = true; minCost[startNode] = -inf;
    primQue.push({-inf, startNode});

    while (!primQue.empty( )) {
            auto node = primQue.top( ).second;
            visited[node] = true; primQue.pop( );
            for (auto nxt : adj[node])
                    if (minCost[nxt.first] > nxt.second && !visited[nxt.first]) {
                            minCost[nxt.first] = nxt.second;
                            parent[nxt.first] = node;
                            primQue.push({-minCost[nxt.first], nxt.first});
                    }

    }
}

int main( ) {
    int numNodes, numEdges; in >> numNodes >> numEdges;

    int nodeA, nodeB, cost;
    for (int i = 0; i < numEdges; ++i) {
        in >> nodeA >> nodeB >> cost;
        adj[nodeA].push_back({nodeB, cost});
        adj[nodeB].push_back({nodeA, cost});
    }

    memset(minCost, inf, sizeof( int ) * (numNodes + 1));
    prim( 1 );

    int ans = 0;
    for (int i = 2; i <= numNodes; ++i) {
            ans += minCost[i];
            toShow.push_back({i, parent[i]});
    }

    out << ans << endl;
    out << toShow.size( ) << endl;
    for (auto edge : toShow) out << edge.first << ' ' << edge.second << endl;
    return 0;
}