#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<int,pair<int,int> > > v,sol;
const int maxn=200005,maxm=400005;
int root[maxn],solfinal,sz[maxn];
int get(int nod)
{
    if(root[nod]==nod)
        return nod;
    return get(root[nod]);
}
void join(int a,int b)
{
    int roota=get(a),rootb=get(b);
    if(sz[roota]<sz[rootb])
        swap(roota,rootb);
    sz[roota]+=sz[rootb];
    root[rootb]=roota;
}
void greedy()
{
    int nod1,nod2,cost,i;
    for(i=0;i<v.size();++i)
    {
        cost=v[i].first;
        nod1=v[i].second.first;
        nod2=v[i].second.second;
        if(get(nod1)!=get(nod2))
        {
            solfinal+=cost;
            join(nod1,nod2);
            sol.push_back(v[i]);
        }
    }
    fout<<solfinal<<'\n'<<sol.size()<<'\n';
    for(i=0;i<sol.size();++i)
    {
        fout<<sol[i].second.first<<' '<<sol[i].second.second<<'\n';
    }
}
int main()
{
    int n,m,i,nod1,nod2,cost;
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>nod1>>nod2>>cost;
        v.push_back({cost,{nod1,nod2}});
    }
    sort(v.begin(),v.end());
    for(i=1;i<=n;++i)
    {
        root[i]=i;
        sz[i]=1;
    }
    greedy();
    return 0;
}