#include<iostream>
#include<queue>
#include<stdio.h>
#include<vector>

using namespace std;

struct coord
{
    int first, second, last_node;

    const bool operator <(const coord &other)const
    {
        return first > other.first;
    }
};

const int NMAX = 2e5 + 5;
int n, m, suma;
vector<pair<int, int>> v[NMAX], ans;
bool viz[NMAX];

void bfs()
{
    priority_queue<coord> q;

    for(auto nod : v[1])
        q.push({nod.first, nod.second, 1});
    viz[1] = true;

    while(!q.empty())
    {
        int cost = q.top().first, next_node = q.top().second, last = q.top().last_node;
        q.pop();

        if(viz[next_node])
            continue;

        ans.push_back({next_node, last});
        viz[next_node] = true;
        suma += cost;

        for(auto nod : v[next_node])
        {
            if(!viz[nod.second])
            {
                q.push({nod.first, nod.second, next_node});
            }
        }
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    cin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        cin >> x >> y >> cost;
        v[x].push_back({cost, y});
        v[y].push_back({cost, x});    
    }

    bfs();

    cout << suma << "\n";
    cout << n - 1 << "\n";

    for(int i = 0; i < ans.size(); i++)
        cout << ans[i].first << " " << ans[i].second << "\n"; 
 }