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

using namespace std;

struct muchie
{
  int x, y, c;
  bool operator ()(const muchie &a, const muchie &b)
  {
      return a.c > b.c;
  }
};

int n, m, sum;
int tata[200010];
vector<muchie> sol;
priority_queue<muchie, vector<muchie>, muchie> q;

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

int get_root(int x)
{
    if(tata[x] == x)
        return x;
    else
    {
        tata[x] = get_root(tata[x]);
        return tata[x];
    }
}

void unite(int rx, int ry) ///unificam arborele de rad x cu cel de rad y
{
    tata[rx] = ry;
}

void kruskal()
{
    for(int i = 1; i <= n; i++)
        tata[i] = i;

    while(!q.empty() && sol.size() < n-1)
    {
        muchie u = q.top();
        q.pop();
        int rx = get_root(u.x), ry = get_root(u.y);
        if(rx != ry)
        {
            sum += u.c;
            sol.push_back(u);
            unite(rx, ry);
        }
    }

}

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;
}