#include <fstream>
#include <list>
#include <queue>
using namespace std;

typedef pair<int, int> pairs;
bool viz[200001];
list<pairs> muchii;
vector<pairs> G[200001];

struct MuchieComp
{
    MuchieComp(int first, int second, int cost)
    {
        this->first = first;
        this->second = second;
        this->cost = cost;
    }

    int first, second, cost;

    bool operator < (const MuchieComp &other) const
    {
        return cost > other.cost;
    }
};

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, costMin;
    fin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].emplace_back(y, c);
        G[y].emplace_back(x, c);
    }

    priority_queue<MuchieComp> Q;

    viz[1] = true;
    for (unsigned int i = 0 ; i < G[1].size(); ++i)
        Q.emplace(1, G[1][i].first, G[1][i].second);

    while (!Q.empty())
    {
        MuchieComp curent = Q.top();
        Q.pop();

        if (!viz[curent.second])
        {
            viz[curent.second] = true;
            muchii.emplace_back(curent.first, curent.second);
            costMin += curent.cost;
            for (unsigned int i = 0 ; i < G[curent.second].size(); ++i)
                Q.emplace(curent.second, G[curent.second][i].first, G[curent.second][i].second);
        }
    }

    fout << costMin << '\n' << muchii.size() << '\n';
    for (list<pairs>::iterator it = muchii.begin(); it != muchii.end(); ++it)
        fout << it->first << ' ' << it->second << '\n';
}