#include <bits/stdc++.h>

using namespace std;

const int nmax=2e5+5;

int tata[nmax],sz[nmax];
vector<pair<int,pair<int,int>>>l;
vector<pair<int,int>>ans;

int supreme_hatz(int x)
{
    int y=x,z=x;
    while(tata[y]!=y)
        y=tata[y];
    tata[z]=y;
    while(z!=tata[z])
    {
        z=tata[z];
        tata[z]=y;
    }
    return y;
}

bool check(int x,int y)
{
    if(supreme_hatz(x)==supreme_hatz(y))
        return true;
    return false;
}

void unite(int x,int y)
{
    int tx=supreme_hatz(x),ty=supreme_hatz(y);
    if(sz[tx]>sz[ty])
    {
        tata[ty]=tx;
        sz[tx]+=sz[ty];
    }
    else
    {
        tata[tx]=ty;
        sz[ty]+=sz[tx];
    }
}

int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n,m,x,y,c;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y>>c;
        l.push_back({c,{x,y}});
    }
    sort(l.begin(),l.end());
    for(int i=1;i<=n;i++)
    {
        tata[i]=i;
        sz[i]=1;
    }
    int s=0;
    for(auto x:l)
        if(check(x.second.first,x.second.second)==false)
        {
            s+=x.first;
            unite(x.second.first,x.second.second);
            ans.push_back(x.second);
        }
    cout<<s<<"\n"<<ans.size()<<"\n";
    for(auto x:ans)
        cout<<x.first<<" "<<x.second<<"\n";
    return 0;
}