#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct kys{int x,y,c;}v[200001];
int t[200001],s[200001],h[200001],n,m,k,sol,i;
bool compare(kys a,kys b)
{
    return a.c<b.c;
}
bool aleg_muchie(int x,int y)
{
    int r1,r2,aux;
    r1=x;r2=y;
    while(r1!=t[r1])r1=t[r1];
    while(r2!=t[r2])r2=t[r2];
    while(x!=r1)
    {
        aux=t[x];
        t[x]=r1;
        x=aux;
    }
    while(y!=r2)
    {
        aux=t[y];
        t[y]=r2;
        y=aux;
    }
    if(r1==r2)return 0;
    if(h[r1]>h[r2])t[r2]=r1;
    else{t[r1]=r2;
    if(h[r1]==h[r2])h[r2]++;}
    return 1;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1,compare);
    for(int i=1;i<=n;i++){t[i]=i;h[i]=1;}
    k=0;i=1;
    while(k<n-1)
    {
        if(aleg_muchie(v[i].x,v[i].y))
        {
            sol+=v[i].c;
            s[++k]=i;
        }
        i++;
    }
    fout<<sol<<'\n'<<k<<'\n';
    for(int i=1;i<=k;i++)
    {
        fout<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';
    }
    return 0;
}