#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");
int n,m,s;
bool viz[200001];
vector<pair<int,int>>rasp;
vector<pair<int,int>>adiacenta[200001];
struct elem
{
    int curent,ant,cost;
    bool operator < (const elem &altu)
    const
    {
        return altu.cost<cost;
    }
};
priority_queue<elem>q;
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 push_elem(int c,int a,int cost)
{
    elem n;
    n.ant = a;
    n.cost= cost;
    n.curent = c;
    q.push(n);
}
void alg_prim()
{
    push_elem(1,0,0);
    while(!q.empty())
    {
        int curent = q.top().curent;
        int ant = q.top().ant;
        int cost_curent = q.top().cost;
        q.pop();

        if(viz[curent])
            continue;

        viz[curent] = 1;
        rasp.push_back({ant,curent});
        s+=cost_curent;
        for(auto x:adiacenta[curent])
        {
            int nod = x.first;
            int cost = x.second;
            if(!viz[nod])
            {
                push_elem(nod,curent,cost);
            }
        }

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