#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 200005;

struct muchie{
    int to, cost;
};

struct nr{
    int node, parent, cost;
    bool operator>( const nr& other ) const{
        return cost > other.cost;
    }
};

vector<muchie> adj[MAXN];
int visited[MAXN];
priority_queue<nr, vector<nr>, greater<nr>> pq;
vector<pair<int, int>> muchii;

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n, m, u, v, c, total, i;
    cin >> n >> m;
    for( i = 0; i < m; i++ ){
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    pq.push({1, 0, 0});
    total = 0;
    while( !pq.empty() && muchii.size() < n ){
        nr x = pq.top();
        pq.pop();
        if( visited[x.node] ) 
          continue;
        visited[x.node] = 1;
        total += x.cost;
        if( x.parent != 0 )
            muchii.push_back({x.parent, x.node});
        for( i = 0; i < adj[x.node].size(); i++ ){
            if( !visited[adj[x.node][i].to] )
                pq.push({adj[x.node][i].to, x.node, adj[x.node][i].cost});
        }
    }
    cout << total << "\n" << muchii.size() << "\n";
    for( i = 0; i < muchii.size(); i++ ){
        cout << muchii[i].first << " " << muchii[i].second << "\n";
    }
    return 0;
}