#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int N=2e5+1;
struct ura{
    int x,y,c;
} v[N];
int t[N];
bool cmp(ura a,ura b)
{
    return (a.c<b.c);
}
int sefsuprem(int x)
{
    if(t[x]!=x)
        return t[x]=sefsuprem(t[x]);
}
void reuniune(int x,int y)
{
    int t1=sefsuprem(x);
    int t2=sefsuprem(y);
    t[t1]=t2;
}
vector<pair<int,int> >vrez;
int main()
{
    int n,m,i,sum=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;i++)
        t[i]=i;
    for(i=1;i<=m;i++)
    {
        if(sefsuprem(v[i].x)!=sefsuprem(v[i].y)){
            reuniune(v[i].x,v[i].y);
            sum+=v[i].c;
            vrez.push_back({v[i].x,v[i].y});
        }
    }
    fout<<sum<<'\n';
    fout<<vrez.size()<<'\n';
    for(auto muchie:vrez)
        fout<<muchie.first<<" "<<muchie.second<<'\n';
    return 0;
}