#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int NMAX = 200001;
vector < pair < int, int > > G[NMAX];
int viz[NMAX],arb[NMAX];
int cost_total = 0;

int N, M;

void read(){
    fin >> N >> M;
    for(int i = 0; i < M; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }
}

priority_queue < pair < int, int > > pq;
int nodes_added = 0;
int l=0;
void prim()
{
    pq.push({0, 1});
    nodes_added = 1;
    
    while(!pq.empty() && nodes_added <= N)
    {
        auto cap = pq.top();
        int nodc = cap.second; 
        int cost = -cap.first;
        
        pq.pop();

        if(viz[nodc]==1)  continue; //trece la urmatoarul intrare in structura repetitiva 
        l++;
        arb[l]=nodc;
        viz[nodc] = 1;
        cost_total = cost_total + cost;
        nodes_added++;

        for(auto nbr: G[nodc])
            if(viz[nbr.first]==0)
                    pq.push({-nbr.second, nbr.first});
    }
    
    fout<<cost_total<<'\n';
    fout<<l-1<<'\n';
    for(int i=1;i<l;i++)
       fout<<arb[i]<<" "<<arb[i+1]<<'\n';
}

int main()
{
    read();
    prim();
    return 0;
}