#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
vector<pair<int,pair<int,int>>>arb;
vector<pair<int,int>>ras;
int n,m,x,y,c,cost,t[200002];
int rad(int nod)
{
    if(nod==t[nod])
        return t[nod];
    t[nod]=rad(t[nod]);
    return t[nod];
}
void unire(int a,int b)
{
    int ra=rad(a);
    int rb=rad(b);
    if(ra!=rb)
        t[ra]=rb;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        t[i]=i;
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y>>c;
        arb.push_back(make_pair(c,make_pair(x,y)));
    }
    sort(arb.begin(),arb.end());
    for(int i=0; i<arb.size(); i++)
    {
        if(rad(arb[i].second.first)!=rad(arb[i].second.second))
        {
            cost+=arb[i].first;
            unire(arb[i].second.first,arb[i].second.second);
            ras.push_back(make_pair(arb[i].second.second,arb[i].second.first));
        }
    }
    cout<<cost<<'\n';
    cout<<ras.size()<<'\n';
    for(int i=0;i<ras.size();i++)
        cout<<ras[i].first<<' '<<ras[i].second<<'\n';
}