#include <bits/stdc++.h>

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

struct muchii
{
    int x,y,cost,set;
};

inline bool cmp(const muchii A,const muchii B)
{
    return A.cost<B.cost;
}
muchii v[400003];
int n,m,t[200003];
void Citire()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].cost;
    fin.close();
    sort(v+1,v+m+1,cmp);
}

inline int FindRoot(int k)
{
    int aux,x;
    aux=k;
    while(t[k]!=0)
        k=t[k];
    while(aux!=k)
    {
        x=t[aux];
        t[aux]=k;
        aux=x;
    }
    return k;
}
inline void Union(int x,int y)
{
    t[x]=y;
}
void Rezolvare()
{
    int costtot=0,x,y,i;
    for(i=1;i<=m;i++)
    {
        x=FindRoot(v[i].x);
        y=FindRoot(v[i].y);
        if(x!=y)
        {
            costtot+=v[i].cost;
            Union(x,y);
            v[i].set=1;
        }
    }
    fout<<costtot<<"\n";
    int cnt=0;
    for(i=1;i<=m;i++)
        if(v[i].set==1) cnt++;
    fout<<cnt<<"\n";
    for(i=1;i<=m;i++)
        if(v[i].set==1) fout<<v[i].x<<" "<<v[i].y<<"\n";
    fout.close();
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}