#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");
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int n, m;
    // in >> n >> m;
    scanf("%d %d", &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;
        scanf("%d %d %d", &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<int> dist(n+1, numeric_limits<int>::max());
    vector<bool> visited(n+1, false);

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

    long long cost = 0;
    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] && pii.second < dist[pii.first])
            {
                pq.push({d, pii.first, pii.second});
                dist[pii.first] = pii.second;
            }
        }
    }

    // out << cost << endl;
    printf("%d\n", cost);
    // out << mst.size() << endl;
    printf("%i\n", mst.size());
    for (auto el : mst)
    {
        // out << el.first << " " << el.second << endl;
        printf("%d %d\n", el.first, el.second);
    }

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