#include <bits/stdc++.h>

using namespace std;

#define MAX_N 200000

struct node
{
    int y, cost;
};

struct edge
{
    int x, y;
};

int n, m, ans;
vector <edge> sol;
vector <pair <int, int> > dist;
bitset <MAX_N + 1> isUsed;
vector <vector <node > > graph;

void solve()
{
    int currentNode = 1, nextNode, distNextNode = INT_MAX;
    dist[currentNode].first = INT_MIN;

    for(int steps = 1; steps < n; steps ++)
    {
        isUsed[currentNode] = 1;
        for(auto neighbour : graph[currentNode])
        {
            if(!isUsed[neighbour.y]  &&  neighbour.cost < dist[neighbour.y].first)
            {
                dist[neighbour.y].first = neighbour.cost;
                dist[neighbour.y].second = currentNode;
            }
        }

        distNextNode = INT_MAX;
        for(int i = 1; i <= n; i ++)
        {
            if(!isUsed[i]  &&  dist[i].first < distNextNode)
            {
                nextNode = i;
                distNextNode = dist[i].first;
            }
        }

        sol.push_back({dist[nextNode].second, nextNode});
        ans += distNextNode;
        currentNode = nextNode;
    }
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

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

    cin >> n >> m;

    graph.resize(n + 1);
    dist.resize(n + 1, {INT_MAX, 0});

    for(int i = 1; i <= m; i ++)
    {
        int x, y, c;
        cin >> x >> y >> c;

        graph[x].push_back({y, c});
        graph[y].push_back({x, c});
    }

    solve();

    cout << ans << "\n" << n - 1 << "\n";
    for(edge x : sol)
    {
        cout << x.x << " " << x.y << "\n";
    }
    return 0;
}