#include <cstdio>
#include <algorithm>

using namespace std;

int n,m,used[200001],nrsol,cost,cnt;
struct muchie { int x,y,cost,da;} z[400001];

bool operator<(muchie x, muchie y)
{
    return x.cost<y.cost;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&z[i].x,&z[i].y,&z[i].cost);
    sort(z,z+m);
    for(int i=0;i<m;i++)
    {
        if(used[z[i].x]==0 && used[z[i].y]==0)
        {
            nrsol++;
            cnt++;
            z[i].da=1;
            used[z[i].x]=used[z[i].y]=cnt;
            cost+=z[i].cost;
        }
        else if(used[z[i].x]!=0 && used[z[i].y]!=0 && used[z[i].x]!=used[z[i].y])
        {
            nrsol++;
            cnt++;
            cost+=z[i].cost;
            z[i].da=1;
            int zz=used[z[i].x]<used[z[i].y]?used[z[i].x]:used[z[i].y];
            int zz1=used[z[i].x]>used[z[i].y]?used[z[i].x]:used[z[i].y];
            for(int j=1;j<m;j++)
                if(used[j]==zz1)
                    used[j]=zz;
        }
        else if(used[z[i].x]!=0 && used[z[i].y]==0 || used[z[i].y]!=0 && used[z[i].x]==0)
        {
            nrsol++;
            cnt++;
            cost+=z[i].cost;
            z[i].da=1;
            if(used[z[i].x]==0)
                used[z[i].x]=used[z[i].y];
            else
                used[z[i].y]=used[z[i].x];
        }
    }
    printf("%d\n%d\n",cost,nrsol);
    for(int i=0;i<m;i++)
        if(z[i].da==1)
            printf("%d %d\n",z[i].x,z[i].y);
    fclose(stdout);
    return 0;
}