#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n,m;

struct st2
{
    int leg, lung;
}tree[100010];

struct st
{
    int m1,m2,cost;
}a[400010];

bool comp (st x, st y)
{
    return (x.cost<y.cost);
}

bool check (int x, int y)
{
int aux=x;
int k;
while (tree[x].leg!=0) x=tree[x].leg;
while (tree[aux].leg!=0) {k=aux;aux=tree[aux].leg;tree[k].leg=x;}

aux=y;
while (tree[y].leg!=0) y=tree[y].leg;
while (tree[aux].leg!=0) {k=aux;aux=tree[aux].leg;tree[k].leg=y;}

if (x!=y) return 1;
return 0;
}


void adauga (int x, int y)
{
while (tree[x].leg!=0) x=tree[x].leg;
while (tree[y].leg!=0) y=tree[y].leg;
if (tree[x].lung>tree[y].lung) tree[y].leg=x;
if (tree[x].lung<tree[y].lung) tree[x].leg=y;
if (tree[x].lung==tree[y].lung)
{
    tree[x].leg=y; tree[y].lung++;
}



}

int main()
{
int i;
int nrt=0;
f>>n>>m;
for (i=1;i<=m;i++)
{
    f>>a[i].m1>>a[i].m2>>a[i].cost;
}
sort (a+1,a+m+1, comp);

for (i=1;i<=m;i++)
{

if (check(a[i].m1, a[i].m2)==1)
{
    //cout<<i<<" ";
    nrt++;
    adauga (a[i].m1,a[i].m2);
    a[nrt].m1=a[i].m1;
    a[nrt].m2=a[i].m2;
    a[0].cost+=a[i].cost;
}

}
g<<a[0].cost<<"\n"<<nrt<<"\n";
for (i=1;i<=nrt;i++)
{
    g<<a[i].m2<<" "<<a[i].m1<<"\n";
}

    return 0;
}