#include <bits/stdc++.h>
#define Nmax 200002
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct Edge{int x,y,cost,used;}E[2*Nmax];
int N,M,i,C,Nr;
int T[Nmax],Rank[Nmax];

bool cmp(Edge A,Edge B)
{
    return A.cost<B.cost;
}

void Read()
{
    f>>N>>M;
    for(i=1;i<=M;i++)
    {
        f>>E[i].x>>E[i].y>>E[i].cost;
    }
}

int Root(int k)
{
    if(T[k]==0)return k;
    int r=Root(T[k]);
    T[k]=r;
    return r;
}

void Union(int x,int y)
{
    int rx=Root(x),ry=Root(y);
    if(rx!=ry)
    {
        Nr++;E[i].used=1;C+=E[i].cost;
        if(Rank[rx]>Rank[ry])T[ry]=rx;
        else
        {
            T[rx]=ry;
            if(Rank[rx]==Rank[ry])Rank[ry]++;
        }
    }
}

void Kruskal()
{
    for(i=1;i<=M;i++)
        Union(E[i].x,E[i].y);
}

void Print()
{
    g<<C<<"\n"<<Nr<<"\n";
    for(i=1;i<=M;i++)
    if(E[i].used==1)g<<E[i].x<<" "<<E[i].y<<"\n";
}
int main()
{
    Read();
    sort(E+1,E+M+1,cmp);
    //for(i=1;i<=M;i++)
        //g<<E[i].x<<" "<<E[i].y<<" "<<E[i].cost<<"\n";
    Kruskal();
    Print();
    return 0;
}