#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 Print()
{
    g << mstCost << "\n";
    g << countedEdges << "\n";
    for (int i = 0; i < vec.size(); i++)
    {
        g << vec[i].first << " " << vec[i].second << "\n";
    }
}

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);

    while (PQ.empty() == false)
    {
        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);

        mstCost += cost;
        countedEdges++;
        vec.push_back(make_pair(at, to));
    }
}

int main()
{
    Read();
    Prim(1);
    Print();
}