#include<iostream>
#include<fstream>
#include<algorithm>
#define DN 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,p1,p2,pr[DN],r[DN],s[DN],nr;
struct leg
{
    int a,b,c;
}x[DN];
int cmp(leg A,leg B)
{
    if(A.c<B.c)
        return 1;
    return 0;
}
int ve(int x)
{
    if(pr[x]==0)
        return x;
    pr[x]=ve(pr[x]);
    return pr[x];
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>x[i].a>>x[i].b>>x[i].c;
    sort(x+1,x+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        p1=ve(x[i].a);
        p2=ve(x[i].b);
        if(p1!=p2)
        {
            pr[p2]=p1;
            r[p1]+=r[p2]+x[i].c;
            s[i]=1;
            nr++;
        }
    }
    p1=ve(1);
    fout<<r[p1]<<'\n'<<nr<<'\n';
    for(int i=1;i<=m;i++)
        if(s[i])
            fout<<x[i].a<<' '<<x[i].b<<'\n';
}