#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int Mmax=4e5+2;
int n,m,t[Mmax];

struct Sex
{
    int x,y,cost;
    bool viz;
};
Sex a[Mmax];

inline bool Compara(Sex A,Sex B)
{
    return A.cost<B.cost;
}

inline void Union(int x,int y)
{
    t[y]=x;
}

inline int Find(int x)
{
    int y,rad=x;

    while(t[rad])
        rad=t[rad];

    while(x!=rad)
    {
        y=t[x];
        t[x]=rad;
        x=y;
    }
    return rad;
}

int main()
{
    fin>>n>>m;

    for(int i=1;i<=m;i++)
        fin>>a[i].x>>a[i].y>>a[i].cost;

    sort(a+1,a+m+1,Compara);

    int x,y,cost;
    cost=0;
    for(int i=1;i<=m;i++)
    {
        x=Find(a[i].x);
        y=Find(a[i].y);

        if(x!=y)
        {
            cost+=a[i].cost;
            a[i].viz=true;
            Union(x,y);
        }
    }

    fout<<cost<<"\n"<<n-1<<"\n";

    for(int i=1;i<=m;i++)
        if(a[i].viz==true)fout<<a[i].x<<" "<<a[i].y<<"\n";

    fin.close();
    fout.close();
    return 0;
}