#include <fstream>
#include <queue>

using namespace std;

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


const int NMAX = 2e5 + 5, MMAX = 4e5 + 5;
bool Seen[NMAX];
priority_queue < pair < int, pair < int, int > > > Queue;
vector < pair < int, int > > Edges[NMAX];
vector < pair < int, int > > APM;
int N, M, cost;

int main()
{
    int x, y, c;
    in >> N >> M;
    for(int i = 1; i <= M; i++)
        in >> x >> y >> c, Edges[x].push_back({y, c}), Edges[y].push_back({x, c});
    for(pair < int, int > it : Edges[1])
        Queue.push({-it.second, {1, it.first}});
    Seen[1] = 1;
    while (!Queue.empty() && APM.size() < N-1)
    {
        c = -Queue.top().first;
        x = Queue.top().second.first;
        y = Queue.top().second.second;
        Queue.pop();
        if(Seen[y])
            continue;
        Seen[y] = 1;
        cost += c;
        for(pair < int, int > it : Edges[y])
            if(!Seen[it.first])
                Queue.push({-it.second, {y, it.first}});
        APM.push_back({x, y});
    }
    out << cost << '\n' << N-1 << '\n';
    for(pair < int, int > it : APM)
        out << it.first << ' ' << it.second << '\n';
    return 0;
}