#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
int n,m;

bool viz[200001];
vector <pair<int,int>> adiacenta[200001];

int suma_min;
queue<pair<int,int>> rasp;

priority_queue<pair<int,pair<int,int>> , vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>>q;
void citire()
{
    f >> n >> m;
    for(int i = 1;i<=m;i++)
    {
        int x,y,c;
        f >> x >> y >> c;
        adiacenta[y].push_back({c,x});
        adiacenta[x].push_back({c,y});
    }
}
void adaugare(int nod)
{
    for(auto x:adiacenta[nod])
    {
        if(!viz[x.second])
        {
            q.push({x.first,{x.second,nod}});
        }
    }
}
void algoritmul_lui_prim()
{
    viz[1] = 1;
    adaugare(1);
    while(!q.empty())
    {
        int nod_curent = q.top().second.first;
        int nod_precedent = q.top().second.second;
        int cost_curent = q.top().first;

        q.pop();
        if(viz[nod_curent])
        {
            continue;
        }
        viz[nod_curent] = 1;

        adaugare(nod_curent);
        suma_min +=cost_curent;
        rasp.push({nod_curent,nod_precedent});

    }
}
void afisare()
{
    g << suma_min<< endl;
    g << rasp.size()<< endl;
    while(!rasp.empty())
    {
        g << rasp.front().first<< " "<< rasp.front().second<< '\n';
        rasp.pop();
    }
}
int main()
{
    citire();
    algoritmul_lui_prim();
    afisare();
    return 0;
}