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

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

const int inf = 0x3f3f3f3f;

struct cmp 
{
    bool operator()(pair<int,int> a, pair<int,int> b) 
    {
        return a.second > b.second;
    }
};

int n, m, cost;
vector<vector<pair<int,int>>> adj_list;
vector<pair<int,int>> mst;
priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> Q;

vector<int> min_cost, parent, visited;

void read() {
    fin >> n >> m;
    adj_list.assign(n + 1, {});
    min_cost.assign(n + 1, inf);
    parent.assign(n + 1, 0);
    visited.assign(n + 1, 0);

    for (int i = 0; i < m; i++) 
    {
        int x, y, c;
        fin >> x >> y >> c;
        adj_list[x].push_back({y, c});
        adj_list[y].push_back({x, c});
    }
}

int main() 
{
    read();

    min_cost[1] = 0;
    Q.push({1, 0});

    while (!Q.empty()) 
    {
        int x = Q.top().first;
        Q.pop();

        if (visited[x]) 
            continue;
        
        visited[x] = 1;

        cost += min_cost[x];
        if (x != 1) 
            mst.push_back({x, parent[x]});

        for (auto &[y, c] : adj_list[x]) 
        {
            if (!visited[y] && c < min_cost[y]) 
            {
                min_cost[y] = c;
                parent[y] = x;
                Q.push({y, c});
            }
        }
    }

    fout << cost << '\n' << mst.size() << '\n';
    for (auto &[u, v] : mst)
        fout << u << ' ' << v << '\n';

    return 0;
}