# include <fstream>
# include <iostream>
# include <algorithm>
# include <vector>
# define nmax 200005

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

struct muchie{int x,y,cost;};
muchie edges[nmax*2];

int root[nmax],
    x[nmax],
    y[nmax],
    c,d,n,m,
    totalCost=0,
    numarPerechi=0;


int findRoot(int a)
{
    return (a==root[a]) ? a : (root[a]=findRoot(root[a]));
}

bool compare(muchie a,muchie b) {return (a.cost<b.cost);}

void read()
{
    fin>>n>>m;
    for (int i=1;i<=m;++i)
    {
        int u,v,auxCost;
        fin>>u>>v>>auxCost;
        edges[i].x=u;
        edges[i].y=v;
        edges[i].cost=auxCost;
    }
}

void initializer()
{
    for (int i=1;i<=n;++i) root[i]=i;
    sort(edges+1,edges+1+m,compare);
}

void kruskal()
{
    for (int i=1;i<=m;++i)
    {
        c=findRoot(edges[i].x);
        d=findRoot(edges[i].y);
        if (c!=d)
        {
            totalCost+=edges[i].cost;
            x[++numarPerechi]=edges[i].x;
            y[numarPerechi]=edges[i].y;
            root[c]=d;
        }
    }
}

void print()
{
    fout<<totalCost<<"\n"<<n-1<<"\n";
    for (int i=1;i<=numarPerechi;++i)
        fout<<y[i]<<" "<<x[i]<<"\n";
}

int main(void)
{
    read();
    initializer();
    kruskal();
    print();
    return 0;
}