#include <fstream>
#include<algorithm>
using namespace std;
ifstream cin ("apm.in");
ofstream cout("apm.out");
int t[200001],rang[200001],k,cost,q,sol[3][400001],n,m;
struct bla
{
    int fx,sx,co;
} s[400001];
bool sortare (bla x,bla y)
{
    return x.co<y.co;
}
void citire ()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
     cin>>s[i].fx>>s[i].sx>>s[i].co;
     sort(s+1,s+m+1,sortare);
}
void init ()
{
    for(int i=1;i<=n;i++)
        t[i]=i;
}
int cauta (int x)
{
    if(t[x]!=x)
        t[x]=cauta(t[x]);
    return t[x];
}
void reunire (int i,int j)
{
    if(i==j) return;
    if(rang[i]<rang[j])
        t[i]=j;
    else t[j]=i;
    if(rang[i]==rang[j]) rang[i]++;
    cost+=s[k].co;
    q++;
    sol[1][q]=s[k].fx;
    sol[2][q]=s[k].sx;

}
void parcurge ()
{
    for(k=1;k<=m;k++)
    {
        int i=cauta(s[k].fx);
        int j=cauta(s[k].sx);
        reunire(i,j);
    }
}
void scrie ()
{
    cout<<cost<<"\n"<<q<<"\n";
    for(int i=1;i<=q;i++)
        cout<<sol[1][i]<<" "<<sol[2][i]<<"\n";
}
int main()
{
    citire();
    init();
    parcurge();
    scrie();
    return 0;
}