#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
pair<int,pair<int,int> > edg[400005];
int n,sz[400005],t[400005],m;
int father(int nod)
{
    if(nod==t[nod])
        return nod;
    return t[nod]=father(t[nod]);
}
void unite(int a, int b)
{
    a=father(a);
    b=father(b);
    if(a==b)return;
    if(sz[a]<sz[b])
        swap(a,b);
    sz[a]+=sz[b];
    sz[b]=0;
    t[b]=a;
}
long long ans;
vector<pair<int,int> > muc;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>edg[i].second.first>>edg[i].second.second>>edg[i].first;
    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        t[i]=i;
    }
    sort(edg+1,edg+m+1);
    for(int i=1;i<=m;i++)
    {
        int a=edg[i].second.first;
        int b=edg[i].second.second;
        if(father(a)!=father(b))
        {
            ans+=edg[i].first;
            unite(a,b);
            muc.push_back(edg[i].second);
        }
    }
    fout<<ans<<'\n'<<muc.size()<<'\n';
    for(auto it:muc)
        fout<<it.first<<' '<<it.second<<'\n';
    return 0;
}