#include <bits/stdc++.h>

using namespace std;

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

int n,m,N,S,t[200009];

struct ceva
{
    int x,y,c,viz;
}v[200009];

int comp(ceva m1,ceva m2)
{
    return (m1.c<m2.c);
}

int Find(int nod)
{
    while (t[nod]!=0) nod=t[nod];
    return nod;
}

void Union(int nod1,int nod2)
{
    t[nod2]=nod1;
}

int main()
{
    in>>n>>m;
    for (int i=1;i<=m;i++) in>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,comp);
    for (int i=1;i<=m && N<n-1;i++)
    {
        int a=Find(v[i].x),b=Find(v[i].y);
        if (a!=b)
        {
            Union(a,b);
            S+=v[i].c;
            v[i].viz=1;
            N++;
        }
    }
    out<<S<<'\n'<<N<<'\n';
    for (int i=1;i<=m;i++)
    {
        if (v[i].viz==1) out<<v[i].y<<" "<<v[i].x<<'\n';
    }
}