#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#pragma GCC optimize ("O4,Ofast")
#pragma GCC optimize ("unroll-loops")
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

const int Nmax = 2e5 + 5, Mmax = 4e5 + 5;

vector<pair<int, int>>g[Nmax];
vector<pair<int, int>> ans;
bool vis[Nmax];

int prim()
{
    int apm = 0;
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    ///                 cost nod curent nod trecut
    pq.push({0, {1, 0}});
    while(!pq.empty())
    {
        int cost = pq.top().first, u = pq.top().second.first, v = pq.top().second.second;
        pq.pop();
        if(vis[u] == 1)
            continue;
        vis[u] = 1;
        apm += cost;
        if(v != 0 && u != 0)
            ans.push_back({v, u});
        for(auto it: g[u])
            if(vis[it.first] == 0)
                pq.push({it.second, {it.first, u}});
    }
    return apm;
}

signed main()
{
    int n, m, i, apm = 0, poz = 0, u, v, c;
    cin >> n >> m;
    for(i = 1; i <= m; i ++)
    {
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    apm = prim();
    cout << apm << '\n';
    cout << ans.size() << '\n';
    for(i = 0; i < ans.size(); i ++)
        cout << ans[i].first << " " << ans[i].second << '\n';
    return 0;
}