#include <bits/stdc++.h>

using namespace std;
int n,m,t[200005],cost,k;
struct elem{
    int x,y,c;
}v[400005],rez[400005];

bool cmp(elem A, elem B)
{
    if(A.c<B.c) return true;
    return false;
}

int Find(int x)
{
    int c=x,aux;
    while(t[c]!=0)
        c=t[c];
    while(t[x]!=0)
    {
        aux=t[x];
        t[x]=c;
        x=aux;
    }
    return c;
}

void Union(int x, int y)
{
    t[x]=y;
}

int main()
{
    int i,a,b;
    ifstream fin("apm.in");
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].c;
    fin.close();
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        a=Find(v[i].x);
        b=Find(v[i].y);
        if(a!=b)
        {
            cost+=v[i].c;
            Union(a,b);
            rez[++k]=v[i];
        }
    }
    ofstream fout("apm.out");
    fout<<cost<<"\n"<<n-1<<"\n";
    for(i=1;i<=k;i++)
        fout<<rez[i].x<<" "<<rez[i].y<<"\n";
    return 0;
}