// https://www.infoarena.ro/problema/apm - Szücs Patrik - Kevin
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

#define vint vector<int>

struct edge
{
    int x, y, cost;

    bool operator<(const edge &a) const
    {
        return cost > a.cost;
    }
};

int main()
{
    int n, m;

    ifstream in("apm.in");
    in >> n >> m;

    vector<edge> edges(m);
    for (int i = 0; i < m; i++)
    {
        in >> edges[i].x >> edges[i].y >> edges[i].cost;
    }

    in.close();

    vector<bool> vis(n + 1);
    vis[1] = true;

    vector<pair<int, int>> ans;
    int s = 0;
    for (int i = 1; i < n; i++)
    {
        int indx = -1, best = INT_MAX;

        for (int j = 0; j < m; j++)
            if (vis[edges[j].x] != vis[edges[j].y] && edges[j].cost < best)
            {
                best = edges[j].cost;
                indx = j;
            }

        int x = edges[indx].x;
        int y = edges[indx].y;

        if (vis[x])
            vis[y] = true;
        else
            vis[x] = true;

        ans.push_back({x, y});
        s += best;
    }

    ofstream out("apm.out");
    out << s << '\n'
        << ans.size();
    for (auto &i : ans)
        out << '\n'
            << i.first << ' ' << i.second;

    return 0;
}