#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct muchie
{
    int x,y,cost;
    bool inApm; 
};

bool mycmp(muchie a,muchie b)
{
    return a.cost < b.cost;
}

struct paduri
{
    vector<int> parent;
    vector<int> size;
    void init(int size)
    {
        parent.resize(size +1);
        this->size.resize(size+1);
        for (int i = 0; i <= size; i++)
        {
            parent[i] = i;
            this->size[i] = 1;
        }
    }

    int rad(int x)
    {
        if (x == parent[x])
        {
            return x;
        }
        parent[x] = rad(parent[x]);
        return parent[x];
    }

    void join(int x, int y)
    {
        x = rad(x);
        y = rad(y);
        if (x != y)
        {
            if (size[x] < size[y])
            {
                parent[x] = y;
                size[y] = size[y] + size[x];
            }
            else
            {
                parent[y] = x;
                size[x] = size[x] + size[y];
            } 
        }
    }

    bool same(int x,int y)
    {
        x = rad(x);
        y = rad(y);
        return x == y;
    }

};

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");

    int n,m;
    in >> n >> m;
    vector<muchie> muchii;

    for (int i = 0; i < m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        muchie aux;
        aux.x = x;
        aux.y = y;
        aux.cost = c;
        muchii.push_back(aux);
    }
    sort(muchii.begin(),muchii.end(),mycmp);
    paduri graf;
    graf.init(n);
    int suma = 0;
    for (int i = 0; i < m; i++)
    {
        if (!graf.same(muchii[i].x,muchii[i].y))
        {
            graf.join(muchii[i].x,muchii[i].y);
            suma = suma + muchii[i].cost;
            muchii[i].inApm = true;
        }
    }
    
    out << suma <<"\n" << n - 1 << "\n";

    for (int i = 0; i < m; i++)
    {
        if (muchii[i].inApm)
        {
            out << muchii[i].x <<" "<< muchii[i].y << "\n";
        }
    }
    

    in.close();
    out.close();
    return 0;
}