#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <functional>

using namespace std;

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

vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> sol;
vector<int> viz;
long long cost_tot = 0; 
int n, m;

void prim(int start)
{
    
    priority_queue<pair<int, pair<int, int>>,
                   vector<pair<int, pair<int, int>>>,
                   greater<pair<int, pair<int, int>>>>
        q;


    q.push({0, {start, -1}});

    while (!q.empty())
    {
        int cost = q.top().first;
        int u = q.top().second.first;
        int p = q.top().second.second;
        q.pop();

        if (viz[u])
            continue;

        viz[u] = 1;
        cost_tot += cost;

        if (p != -1)
        {
            sol.push_back({p, u});
        }

        for (auto edge : adj[u])
        {
            int w = edge.first;
            int v = edge.second;
            if (!viz[v])
            {
               
                q.push({w, {v, u}});
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    adj.assign(n + 1, {});
    viz.assign(n + 1, 0);

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

    prim(1);

    fout << cost_tot << "\n";
    fout << sol.size() << " \n";
    for (auto e : sol)
    {
        fout << e.first << " " << e.second << "\n";
    }
    return 0;
}