# include <cstdio>
# include <algorithm>
# include <vector>

const int max_n = 400005;

using namespace std;

int sum, n, m, i, ct;
int a[max_n], b[max_n], c[max_n], ind[max_n], comp[max_n], v[max_n];

int grupa(int i)
{
    if (comp[i] == i) return i;
    comp[i] = grupa(comp[i]);
    return comp[i];
}

void lafel(int i, int j)
{
     comp[grupa(i)] = grupa(j);
}     

int cmp(int i, int j)
{
    return (c[i] < c[j]);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        ind[i] = i;
        }
        
    for (i = 1; i <= n; i++)
        comp[i] = i;
        
    sort(ind + 1, ind + m + 1, cmp);

    for (i = 1; i <= m; i++)
        if (grupa(a[ind[i]]) != grupa(b[ind[i]]))
        {
              sum += c[ind[i]];
              lafel(a[ind[i]],b[ind[i]]);
              v[++ct] = ind[i];
              }

     printf("%d\n",sum);
     printf("%d\n",n - 1);
     for (i = 1; i <= n - 1; i++)
     printf("%d %d\n",a[v[i]],b[v[i]]);
     
return 0;
}