#include <fstream>
#include <algorithm>
using namespace std;
struct Nr
{
    int a,b,c;
}M[4000005];
int cmp(Nr x,Nr y)
{
    return x.c<y.c;
}
int T[200005],depth[200005];
int root(int x)
{
    if(T[x]==x)
        return x;
    T[x]=root(T[x]);
    return T[x];
}
void UNION(int a,int b)
{
    a=root(a);
    b=root(b);
    if(depth[a]==depth[b])
    {
        T[a]=b;
        depth[b]++;
    }
    else if(depth[a]<depth[b])
    {
        T[a]=b;
    }
    else
    {
        T[b]=a;
    }
}
int used[200005];
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>M[i].a>>M[i].b>>M[i].c;
    }
    sort(M+1,M+m+1,cmp);
    for(int i=1;i<=n;i++)
        T[i]=i,depth[i]=1;
    int counter=0,s=0;
    for(int i=1;i<=m;i++)
    if(counter<n-1)
    {
        int x=M[i].a,y=M[i].b,c=M[i].c;
        if(root(x)!=root(y))
        {
            counter++;
            s+=c;
            used[i]=1;
            UNION(x,y);
        }
    }
    else
        break;
    cout<<s<<"\n"<<counter<<"\n";
    for(int i=1;i<=m;i++)
        if(used[i]==1)
        {
            int x=M[i].a,y=M[i].b;
            cout<<x<<" "<<y<<'\n';
        }
    return 0;
}