#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX=2*1e5+5;
int t[NMAX],sz[NMAX];
struct muchie
{
 int u,v,c;
};
bool cmp(muchie a,muchie b){return a.c<b.c;}
vector<muchie>v;
vector<muchie>rez;
int rad(int x){if(t[x]!=x)t[x]=rad(t[x]);return t[x];}
void un(int a,int b)
{
    a=rad(a);
    b=rad(b);
    if(sz[a]<sz[b])swap(a,b);
    sz[a]+=sz[b];
    t[b]=a;
}
int main()
{
    int n,q;
    fin>>n>>q;
    for(int i=1;i<=n;i++){sz[i]=1;t[i]=i;}
    for(int i=1;i<=q;i++)
    {
        muchie x;
        fin>>x.u>>x.v>>x.c;
        v.push_back(x);
        swap(x.u,x.v);
        v.push_back(x);
    }
    int ans=0;
    sort(v.begin(),v.end(),cmp);
    for(auto i:v)
    {
        int a=i.u;
        int b=i.v;
        int cost=i.c;
        if(rad(a)!=rad(b))
        {
            un(a,b);
            ans+=cost;
            rez.push_back({a,b});
        }
    }
    fout<<ans<<'\n';
    fout<<rez.size()<<'\n';
    for(muchie i:rez)fout<<i.u<<" "<<i.v<<'\n';
}