#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");
int n,m;
struct muchie{
    int x,y,cost;
}v[400001];
int tata[200001],drum1[200001],drum2[200001];
bool cmp(muchie a,muchie b)
{
    if(a.cost<b.cost)
        return true;
    else
            return false;
}
int sef(int x)
{
    if(x==tata[x])
        return x;
    else
        return tata[x]=sef(tata[x]);
}
void unire(int x,int y)
{
    int s1,s2;
    s1=sef(x);
    s2=sef(y);
    tata[s2]=s1;
}
int main()
{
    int i;
    cin>>n>>m;
    for(i=1;i<=m;i++)
        cin>>v[i].x>>v[i].y>>v[i].cost;
    sort(v+1,v+1+m,cmp);
    for(i=1;i<=n;i++)
        tata[i]=i;
    int cnt=0,cost=0,pp=1;
    for(i=1;i<=m and pp==1;i++)
    {
        if(cnt<n-1)
        {
            if(sef(v[i].x)!=sef(v[i].y))
            {
                cnt++;
                drum1[cnt]=v[i].x;
                drum2[cnt]=v[i].y;
                unire(v[i].x,v[i].y);
                cost+=v[i].cost;
            }
        }
        else
            pp=0;
    }
    cout<<cost<<"\n"<<n-1<<"\n";
    for(i=1;i<=cnt;i++)
        cout<<drum2[i]<<" "<<drum1[i]<<"\n";
    return 0;
}