#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int N=2e5+10;
struct muchie{
    int x,y,z;
    bool operator < (const muchie& other) const
    {
        return z < other.z;
    }
};
vector <muchie> a;
vector <muchie> afisare;
int tata[N],n,nrp[N];
int radacina(int x)
{
    if(tata[x]==0)
    {
        return x;
    }
    tata[x]=radacina(tata[x]);
    return tata[x];
}
bool interogare(int x,int y)
{
    return (radacina(x)==radacina(y));
}
void reuniune(int x,int y)
{
    int rx=radacina(x);
    int ry=radacina(y);
    if(nrp[rx]<nrp[ry])
    {
        tata[rx]=ry;
        nrp[ry]+=nrp[rx];
    }
    else
    {
        tata[ry]=rx;
        nrp[rx]+=nrp[ry];
    }
}
int main()
{
    int m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        muchie aux;
        f>>aux.x>>aux.y>>aux.z;
        a.push_back(aux);
    }
    for(int i=1;i<=n;i++)
    {
        tata[i]=0;
        nrp[i]=1;
    }
    sort(a.begin(),a.end());
    int rez=0;
    for(auto i:a)
    {
        if(!interogare(i.x,i.y))
        {
            rez+=i.z;
            afisare.push_back(i);
            reuniune(i.x,i.y);
        }
    }
    g<<rez<<"\n"<<afisare.size()<<"\n";
    for(auto i:afisare)
    {
        g<<i.y<<" "<<i.x<<"\n";
    }
    return 0;
}