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

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    int x,y,cost;
    friend bool operator >(const muchie&,const muchie&);
};

bool operator >(const muchie& m1,const muchie& m2)
{
    return m1.cost>m2.cost;
}
priority_queue<muchie,vector<muchie>,greater<muchie> >H;
int tat[200002],h[200002];
vector<muchie>sol;
int soli;
int n,m;

int Find(int x)
{
    int r=x;
    while(tat[r])
        r=tat[r];
    int y=x,aux;
    while(y!=r)
    {
        aux=tat[y];
        tat[y]=r;
        y=aux;
    }
    return r;
}

void Union(int c1,int c2)
{
    if(h[c1]>h[c2])
    {
        tat[c2]=c1;
    } else {
        tat[c1]=c2;
        if(h[c1]==h[c2])
            h[c2]++;
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        muchie m;
        f>>m.x>>m.y>>m.cost;
        H.push(m);
    }
    while(sol.size()<n-1)
    {
        muchie m=H.top();
        H.pop();
        int c1=Find(m.x);
        int c2=Find(m.y);
        if(c1!=c2)
        {
            Union(c1,c2);
            soli+=m.cost;
            sol.push_back(m);
        }
    }
    g<<soli<<'\n';
    g<<sol.size()<<'\n';
    for(int i=0;i<sol.size();++i)
        g<<sol[i].x<<' '<<sol[i].y<<'\n';
}