#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct MUCHIE
{
    int x,y,c;
    bool sel;
};
vector <MUCHIE> v;
vector <int> t,h;
bool cmp(const MUCHIE &a, const MUCHIE &b)
{
    return a.c<b.c;
}
int radacina(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}
void unifica(int x, int y)
{
    if(h[x]>h[y])
        t[y]=x;
    else if(h[y]>h[x])
        t[x]=y;
    else
    {
        h[x]++;
        t[y]=x;
    }
}
int main()
{
    int n,m,i,cnt=0,rx,ry,cost=0;
    fin>>n>>m;
    MUCHIE temp;
    t.assign(n+1,0);
    h.assign(n+1,1);
    for(i=1;i<=n;++i)
        t[i]=i;
    temp={0,0,0,0};
    v.push_back(temp);
    for(i=1;i<=m;++i)
    {
        fin>>temp.x>>temp.y>>temp.c;
        temp.sel=0;
        v.push_back(temp);
    }
    sort(v.begin()+1,v.end(),cmp);
    for(i=1;i<=m && cnt<n-1;++i)
    {
        rx=radacina(v[i].x);
        ry=radacina(v[i].y);
        if(rx!=ry)
        {
            unifica(rx,ry);
            v[i].sel=1;
            cost+=v[i].c;
            cnt++;
        }
    }
    fout<<cost<<"\n"<<cnt<<"\n";
    for(i=1;i<=m;++i)
    {
        if(v[i].sel)
            fout<<v[i].y<<" "<<v[i].x<<"\n";
    }
    return 0;
}