#include <iostream>
#include <fstream>
#include<queue>
#include <vector>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
vector<pair<int,int>>adiacenta[200001];
priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>q;
vector<pair<int,int>>rasp;
int cost;
int n,m;
bool viz[200001];
void citire()
{
    f >> n >> m;
    for(int i =1;i<=m;i++)
    {
        int x,y,c;
        f >> x >> y >> c;
        adiacenta[x].push_back({y,c});
        adiacenta[y].push_back({x,c});
    }
}
void Prim()
{
    q.push({0,{0,1}});
    while(!q.empty())
    {
        int curent =q.top().second.second;
        int fost_nod = q.top().second.first;
        int cost_curent = q.top().first;
        q.pop();

        //vizitam acum pentru ca nu luam toti vecinii la un anumit nod
        // ci doar pe unii cu cost minim
        if(viz[curent])
            continue;

        viz[curent] = 1;
        cost+=cost_curent;
        rasp.push_back({curent,fost_nod});
        for(auto x : adiacenta[curent])
        {
            if(!viz[x.first])
            {
                q.push({x.second,{curent,x.first}});
            }
        }
    }
}
void afisare()
{

    g << cost<<'\n'<<rasp.size()-1<<'\n';
    for(int i = 1;i<rasp.size();i++)
        g << rasp[i].first<< " "<< rasp[i].second<< endl;
}
int main()
{
    citire();
    Prim();
    afisare();
}