#include <fstream>
#include <algorithm>

using namespace std;

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


int parent[200050];

struct Heap{
int nod1,nod2,cost;
bool operator<(Heap x) const
{
    return cost < x.cost;
}
}heap[400050],tmp;

int nr,n,m,i,a,b,cost;

struct muchii{int nod1,nod2;}muchii[200050];


int link(int child)
{
    if(parent[child]==0)
        return child;
    return parent[child]=link(parent[child]);
}

void link(int a,int b)
{
        parent[link(b)]=link(a);

}


bool check(int x,int y)
{
    if(link(x)==link(y))
        return 0;
    return 1;
}


int main()
{

    fin>>n>>m;

    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>cost;

        tmp.nod1=a;
        tmp.nod2=b;
        tmp.cost=cost;

        heap[i]=tmp;

    }

    sort(heap+1,heap+1+m);

    cost=0;
    int x=0;

    for(i=1;i<=m;i++)
    {
        if(check(heap[i].nod1,heap[i].nod2))
        {

        link(heap[i].nod1,heap[i].nod2);
            cost+=heap[i].cost;

            muchii[++x].nod1=heap[i].nod1;
            muchii[x].nod2=heap[i].nod2;
        }
    }

    fout<<cost<<'\n'<<x<<'\n';

    for(i=1;i<=x;i++)
        fout<<muchii[i].nod1<<' '<<muchii[i].nod2<<'\n';

    return 0;
}