#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,s,nr;
struct edge
{
    int a,b,c;
    bool u;
} z[400001];
int v[200001];

int cmp (edge a, edge b)
{
    return (a.c<b.c);
}

void reunion (int i)
{
    int x=z[i].a,y=z[i].b,temp;
    while (v[x]!=0) x=v[x];
    while (v[y]!=0) y=v[y];
    if (x!=y)
    {
        x=z[i].a;
        while (x!=0)
        {
           temp=v[x];
           v[x]=y;
           x=temp;
        }
        s=s+z[i].c;
        z[i].u=1;
        nr++;
    }
}

int main()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=m;i++) fin>>z[i].a>>z[i].b>>z[i].c;
    sort (z+1,z+m+1,cmp);
    for (i=1;i<=m&&nr<=n-1;i++) reunion (i);
    fout<<s<<"\n"<<n-1<<"\n";
    for (i=1;i<=m;i++)
    {
        if (z[i].u) fout<<z[i].a<<" "<<z[i].b<<"\n";
    }
}