#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <bitset>
#define NMAX 200002

using namespace std;

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

int n,m, total;
vector <pair<int,int>> g[NMAX], rez;
priority_queue <pair<int,pair<int,int>>> q;
bitset <NMAX> viz;

void citire()
{
    f >> n >> m;
    int x,y,c;
    for(int i = 1; i <= m; ++i)
    {
        f >> x >> y >> c;
        g[x].push_back({y,c});
        g[y].push_back({x,c});
    }
}

void prim()
{
    viz[1] = true;
    for(auto i: g[1])
        q.push({-i.second,{i.first, 1}});

    while(not q.empty())
    {
        int cost = -q.top().first;
        int nod = q.top().second.first;
        int tata = q.top().second.second;

        q.pop();
        if(viz[nod])
            continue;
        viz[nod] = true;
        total += cost;

        rez.push_back({nod,tata});
        for(auto i: g[nod])
            if(not viz[i.first])
                q.push({-i.second,{i.first,nod}});
    }
}

void afish()
{
    o << total << '\n';
    o << rez.size() << '\n';
    for(auto i: rez)
        o << i.first << ' ' << i.second << '\n';
}

int main()
{
    citire();
    prim();
    afish();
    return 0;
}