/**
Sorteaza muchiile crescator. Parcurge muchiile, alegand fiecare muchie
care nu creeaza un ciclu in graf. Pentru a verifica, foloseste o padure de
multimi disjuncte, implementata printr-un vector de tati. Cand se alege o
noua muchie, cele doua multimi disjuncte ale nodurilor muchiei sunt
conectate, arborele cu greutate mai mica (adancime mai mica) se conecteaza
la cel cu greutate mai mare. la sfarsit, o sa ramana un graf cu n-1 muchii.
*/
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int n,m,daddy[200000], rang[200000];

struct Edge {
    int x,y,cost;
    bool operator<(const Edge& other) const {
        return cost<other.cost;
    }
}muchii[400000], out[400000];

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

void citire ()
{
    fin>>n>>m;
    for (int i=1;i<=m;i++)
        fin>>muchii[i].x>>muchii[i].y>>muchii[i].cost;

    for (int i=1;i<=n;i++)
    {
        daddy[i]=i;
        rang[i]=1;
    }
}

int findroot (int x)
{
    int root=daddy[x];
    while (root!=daddy[root])
            root=daddy[root];
    while (daddy[x]!=x)
    {
        int aux=daddy[x];
        daddy[x]=root;
        x=aux;
    }
    return root;
}

void add_tree (int x, int y)
{
    if (rang[y]<rang[x])
        daddy[findroot(y)]=findroot(x);

    else
        daddy[findroot(x)]=findroot(y);

    if (rang[y]==rang[x])
        rang[y]++;
    ///adauga un vector de ranguri si muta root-ul de la cel cu rangul mai mic
}

void solve ()
{
    int costfinal=0, k=1;
    for (int i=1;i<=m;i++)
    {
        if (findroot(muchii[i].x)!=findroot(muchii[i].y))
        {
            add_tree(muchii[i].x, muchii[i].y);
            costfinal+=muchii[i].cost;
            out[k++]=muchii[i];
        }
    }
    fout<<costfinal<<"\n"<<n-1<<"\n";
    for (int i=1;i<n;i++)
        fout<<out[i].x<<" "<<out[i].y<<"\n";
}

int main()
{
    citire();
    sort(muchii+1,muchii+m+1);
    solve();
    return 0;
}