#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int NMAX = 2 * 1e5;
vector<pair<int, int> > muchii;
bitset<NMAX + 5> viz;
int n, m;

struct date
{
    int node;
    int cost;
};
vector<date> g[NMAX + 5];

struct point
{
    int current_node;
    int previous_node;
    int cost;

    bool operator < (const point& a) const
    {
        return cost > a.cost;
    }
};
priority_queue<point> q;

void prim()
{
    int weight = 0;
    q.push({1, 0, 0});

    while(!q.empty() && muchii.size() < n - 1)
    {
        point top = q.top();
        int node = top.current_node;
        int prev = top.previous_node;
        int c = top.cost;
        q.pop();

        if(viz[node])
            continue;

        weight += c;
        viz[node] = 1;

        if(prev != 0)
        {
            muchii.push_back({prev, node});
        }

        for(auto it : g[node])
        {
            if(!viz[it.node])
                q.push({it.node, node, it.cost});
        }
    }

    out << weight << '\n';
    out << muchii.size() << '\n';

    for(auto it : muchii)
    {
        out << it.first << ' ' << it.second << '\n';
    }
}

int main()
{
    in >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        int u, v, c;

        in >> u >> v >> c;

        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }

    prim();
    return 0;
}