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

using namespace std;

struct muchie
{
  int x, y, c;
  static bool cmp(const muchie &a, const muchie &b)
  {
      return a.c < b.c;
  }
}u[400010];

int n, m, sum;
int comp[200010];
vector<muchie> sol;

void citire()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &u[i].x, &u[i].y, &u[i].c);
    }
}

void kruskal()
{
    sort(u, u+m, muchie::cmp);
    for(int i = 1; i <= n; i++)
        comp[i] = i;

    for(int i = 0; i < m && sol.size() < n-1; i++)
        if(comp[u[i].x] != comp[u[i].y])
        {
            sum += u[i].c;
            sol.push_back(u[i]);
            int aux1 = comp[u[i].y], aux2 = comp[u[i].x];
            for(int j = 1; j <= n; j++)
                if(comp[j] == aux1)
                    comp[j] = aux2;
        }
}

void afisare()
{
    printf("%d\n%d\n", sum, sol.size());
    for(int i = 0; i < sol.size(); i++)
        printf("%d %d\n", sol[i].x, sol[i].y);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    citire();
    kruskal();
    afisare();
    return 0;
}