#include <bits/stdc++.h>
#define dim 450000
using namespace std;

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


int t[dim];
int rang[dim];
int n,m,total;

struct muchie{

    int x,y,ct;
};

struct rezultat
{
    int first;
    int second;
};

muchie g[dim];
rezultat p[dim];

bool comp(muchie a,muchie b)
{
    return a.ct<b.ct;
}

void read()
{
    fin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        fin>>g[i].x>>g[i].y>>g[i].ct;
    }
    sort(g+1,g+1+m,comp);
}

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

void legatura(int x,int y)
{
    if (rang[x]<rang[y])
    {
        t[x]=y;
    }
    if (rang[x]>rang[y]) t[y]=x;
    if (rang[x]==rang[y])
    {
        t[x]=y;
        rang[x]++;
    }
}


void kruskal()
{
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        t[i]=i;
        rang[i]=1;
    }
    for (int i=1;i<=m;i++)
    {
        int a=tata(g[i].x);
        int b=tata(g[i].y);
        if (a!=b)
        {
            total+=g[i].ct;
            p[++cnt].first=g[i].x;
            p[cnt].second=g[i].y;
            legatura(a,b);
        }
    }
    fout<<total<<'\n'<<cnt<<'\n';
    for (int i=1;i<=cnt;i++)
    {
        fout<<p[i].first<<' '<<p[i].second<<'\n';
    }
}

int main()
{
    read();
    kruskal();
}