#include <fstream>
#include <queue>
#include <vector>
#include <list>
#include <limits>

using namespace std;

struct edge
{
    int source;
    int dest;
    int cost;
};

struct cmp
{
    bool operator() (const edge &a, const edge &b)
    {
        return a.cost < b.cost;
    }
};

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");

    int n, m;
    in >> n >> m;
    
    vector<list<pair<int, int> > > adj(n+1);

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

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

    priority_queue<edge, vector<edge>, cmp> pq;
    vector<bool> visited(n+1, false);

    for (auto pii : adj[1])
    {
        pq.push({1, pii.first, pii.second});
    }
    visited[1] = true;

    long long cost = 0;
    vector<int> dist(n+1, numeric_limits<int>::max());
    vector<pair<int, int> > mst;

    while (!pq.empty())
    {
        edge e = pq.top();
        pq.pop();

        int s = e.source;
        int d = e.dest;
        int c = e.cost;

        if (visited[d])
            continue;

        visited[d] = true;

        cost += c;
        mst.push_back({s, d});

        for (auto pii :  adj[d])
        {
            if (!visited[pii.first])
            {
                pq.push({d, pii.first, pii.second});
            }
        }
    }

    out << cost << endl;
    out << mst.size() << endl;
    for (auto el : mst)
    {
        out << el.first << " " << el.second << endl;
    }

    in.close();
    out.close();
}