#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m;
struct elem_arbore
{
    int nod_curent, nod_urm, cost;
};
vector <elem_arbore> rasp;
int v[200009];
class Heap
{
public:
    int mnod_curent, mnod_urm, mcost;
    Heap(int nod_curent, int nod_urm, int cost)
    {
        mnod_curent=nod_curent;
        mnod_urm=nod_urm;
        mcost=cost;
    }
    bool operator <(const Heap & other)const
    {
        return other.mcost<mcost;
    }
};
priority_queue <Heap> heap;
vector <elem_arbore> vect[400009];
int cost_final;
void apm()
{
    while(!heap.empty())
    {
        Heap primul=heap.top();
        int x=primul.mnod_curent;
        int y=primul.mnod_urm;
        int c=primul.mcost;
        heap.pop();
        if(v[y]==1)
        {
            continue;
        }
        v[y]=1;
        elem_arbore nou;
        nou.nod_curent=x;
        nou.nod_urm=y;
        nou.cost=c;
        cost_final+=c;
        rasp.push_back(nou);
        for(int i=0;i<vect[y].size();i++)
        {
            elem_arbore vecin=vect[y][i];
            heap.push(Heap(vecin.nod_curent,vecin.nod_urm,vecin.cost));
            //cout<<vecin.nod_curent<<' '<<vecin.nod_urm<<' '<<vecin.cost<<endl;
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        elem_arbore nou;
        nou.cost=c;
        nou.nod_curent=x;
        nou.nod_urm=y;
        vect[x].push_back(nou);

        nou.nod_curent=y;
        nou.nod_urm=x;
        vect[y].push_back(nou);
        //heap.push(Heap(x,y,c));
        //heap.push(Heap(y,x,c));
    }
    heap.push(Heap(-1,1,0));
    apm();
    fout<<cost_final<<'\n';
    fout<<rasp.size()-1<<'\n';
    for(int i=1;i<rasp.size();i++)
    {
        fout<<rasp[i].nod_curent<<' '<<rasp[i].nod_urm<<'\n';
    }
    return 0;
}