#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 200002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct two{
    int f,s;
};

struct nod{
    int v1,v2,c;
};

vector <nod> mu;
vector <two> sol;
int r[nmax],t[nmax];

bool cmp(nod A,nod B)
{
    return A.c<B.c;
}

int drum(int x)
{
    int y,r;
    y=x;
    r=x;
    while(r!=t[r])
        r=t[r];
    while(x!=r)
    {
        y=t[x];
        t[x]=r;
        x=y;
    }
    return r;
}

void uneste(int x,int y)
{
    if(r[x]<r[y])
        t[x]=t[y];
    else
        t[y]=t[x];
    if(r[x]==r[y])
        r[x]++;
}

int main()
{
    int n,m,nr_mu=0,sum=0,x,y,c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        mu.push_back({x,y,c});
    }
    sort(mu.begin(),mu.end(),cmp);
    for(int i=1;i<=n;i++)
    {
        r[i]=1;
        t[i]=i;
    }
    for(int i=0;i<m;i++)
    {
        int x=mu[i].v1;
        int y=mu[i].v2;
        int c2=mu[i].c;
        int rx=drum(x);
        int ry=drum(y);
        if(rx!=ry)
        {
            nr_mu++;
            sum+=c2;
            sol.push_back({x,y});
            uneste(rx,ry);
        }
    }
    fout<<sum<<"\n"<<nr_mu<<"\n";
    for(int i=0;i<nr_mu;i++)
        fout<<sol[i].f<<" "<<sol[i].s<<"\n";
    return 0;
}