#include <bits/stdc++.h>

using namespace std;

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

struct muchie
{
    int cost, x, y;
};

struct cmp
{
    bool operator()(muchie a, muchie b)
    {
        return a.cost > b.cost;
    }
};

int main()
{
    int n, m;
    fin >> n >> m;

    vector<vector<pair<int, int>>> v(n + 1);
    vector<bool> vis(n + 1);
    vector<pair<int, int>> sol;
    int sum = 0;

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

        v[x].push_back(make_pair(y, c));
        v[y].push_back(make_pair(x, c));
    }

    priority_queue<muchie, vector<muchie>, cmp> q;

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

    while (!q.empty())
    {
        muchie aux = q.top();

        q.pop();

        if (vis[aux.y])
            continue;

        vis[aux.y] = true;
        sum += aux.cost;
        sol.emplace_back(aux.x, aux.y);

        for (auto i: v[aux.y])
        {
            if (!vis[i.first])
                q.push(muchie{i.second, aux.y, i.first});
        }
    }

    fout << sum << "\n" << sol.size() << "\n";
    for (auto i: sol)
    {
        fout << i.first << " " << i.second << "\n";
    }

    return 0;
}