///! refaci APM
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#define NMAX 200002

using namespace std;

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

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

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 prim()
{
    viz[1] = true;
    for(auto i: g[1])
        q.push({-i.second,{i.first,1}});

    int nod, dad, cost;
    for(int i = 2; i <= n; ++i)
    {
        while(viz[q.top().second.first])
            q.pop();

        cost = -q.top().first;
        nod = q.top().second.first;
        dad = q.top().second.second;
        q.pop();

        viz[nod] = true;

        f_list.push_back({dad,nod});
        f_cost += cost;

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

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

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