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

using namespace std;

int dad[NMAX], _rank[NMAX],n,m, total_cost;
vector <pair<int,int>> g[NMAX], finish;
priority_queue <pair<int,pair<int,int>>> q;
bitset <NMAX> viz;

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

void input()
{
    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 prep()
{
    for(int i = 1; i <= n; ++i)
    {
        dad[i] = i;
        _rank[i] = 1;
    }
}

int get_set(int nod)
{
    int aux = nod, aux2;

    while(aux != dad[aux])
        aux = dad[aux];

    while(nod != dad[nod])
    {
        aux2 = dad[nod];
        dad[nod] = aux;
        nod = aux2;
    }

    return aux;
}

void unite(int n1, int n2)
{
    if(_rank[n1] > _rank[n2])
        dad[n2] = n1;
    else
        dad[n1] = n2;
    if(_rank[n1] == _rank[n2])
        ++ _rank[n2];
}

void prim()
{
    viz[1] = true;
    for(auto i: g[1])
    {
        //cout << i.first << " " << i.second << '\n';
        q.push({-i.second,{1,i.first}});
    }

    int t = 1;
    int nod, nod_dad, cost, gr1, gr2;
    while(t != n)
    {
        while(viz[q.top().second.second])
            q.pop();
        cost = -q.top().first;
        nod_dad = q.top().second.first;
        nod = q.top().second.second;
        q.pop();

        viz[nod] = true;

        gr1 = get_set(nod);
        gr2 = get_set(nod_dad);

        unite(gr1,gr2);
        total_cost += cost;
        finish.push_back({nod_dad, nod});
        ++ t;

        for(auto i: g[nod])
            if(i.first != nod_dad)
                q.push({-i.second,{nod,i.first}});
    }
}

void output()
{
    o << total_cost << '\n';
    o << finish.size() << '\n';
    for(auto i: finish)
        o << i.first << ' ' << i.second << '\n';
}

int main()
{
    input();
    prep();
    prim();
    output();
    return 0;
}