#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,s;
struct edge
{
    int a,b,c;
} 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;
    while (v[x]!=0) x=v[x];
    while (v[y]!=0) y=v[y];
    if (x!=y)
    {
        v[x]=y;
        s=s+z[i].c;
    }
}

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;i++) reunion (i);
    fout<<s<<"\n"<<n-1<<"\n";
    for (i=1;i<=n;i++)
    {
        if (v[i]==0) continue;
        fout<<i<<" "<<v[i]<<"\n";
    }
}