#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f ("apm.in");
ofstream g ("apm.out");

const int SIZE = 200001;

int n, m, mstCost, countedEdges;
bool visited[SIZE];
vector <pair <int, int>> V[SIZE];
vector <pair <int, int>> vec;

struct CompareCost
{
    bool operator()(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y)
    {
        return x.second > y.second;
    }
};
priority_queue<int, vector<pair<pair<int,int>,int>>, CompareCost> PQ;

void Read()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        f >> x >> y >> z;
        V[x].push_back(make_pair(y, z));
        V[y].push_back(make_pair(x, z));
    }
}

void AddEdges(int node)
{
    for (int i = 0; i < V[node].size(); i++)
    {
        int neighbour = V[node][i].first;
        if (visited[neighbour] == false)
        {
            int cost = V[node][i].second;
            PQ.push(make_pair(make_pair(node, neighbour), cost));
        }
    }
}

void Prim(int startNode)
{
    visited[startNode] = true;
    AddEdges(startNode);

    int edges = n - 1;

    while (PQ.empty() == false && countedEdges != edges)
    {
        int at = PQ.top().first.first;
        int to = PQ.top().first.second;
        int cost = PQ.top().second;
        PQ.pop();

        if (visited[to] == true)
        {
            continue;
        }
        visited[to] = true;
        AddEdges(to);

        countedEdges++;
        mstCost += cost;

        vec.push_back(make_pair(at, to));
    }
}

int main()
{
    Read();
    Prim(1);
    g << mstCost << "\n";
    g << countedEdges << "\n";
    for (int i = 0; i < vec.size(); i++)
    {
        g << vec[i].first << " " << vec[i].second << "\n";
    }

//    cout << "\n";
//    while (PQ.empty() == false)
//    {
//        cout << PQ.top().first.first << " " << PQ.top().first.second << " " << PQ.top().second << "\n";
//        PQ.pop();
//    }

//    cout << "\n";
//    for (int i = 1; i <= n; i++)
//    {
//        cout << "Node " << i << " : ";
//        for (int j = 0; j < V[i].size(); j++)
//        {
//            cout << V[i][j].first << "(" << V[i][j].second << ") ";
//        }
//        cout << "\n";
//    }
}