#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <cstdio>
 
 
using namespace std;
 
class ComparatorMuchie;
 
class muchie
{
    friend ostream & operator << (ostream &, const muchie &);
    friend ComparatorMuchie;
 
public:
    int start, end;
    int cost;
     
public:
    muchie(int start, int end, int cost)
    : start(start), end(end), cost(cost)
    {}
     
    int either();
    int other(int);
    int getCost() { return cost; }
     
    void incr() { start++; end++; }
    void decr() { start--; end--; }
};
 
int muchie::either()
{
    return start;
}
 
int muchie::other(int vf)
{
    if (vf == start)
        return end;
    return vf;
}
 
ostream & operator << (ostream & out, const muchie & m)
{
    out << m.end << " " << m.start << '\n';
    return out;
}
 
ostream & operator << (ostream & out, const muchie * m)
{
    out << m->end << " " << m->start << '\n';
    return out;
}
 
 
class ComparatorMuchie
{
public:
    bool operator ()(const muchie * m1, const muchie * m2)
    {
        return m1->cost > m2->cost;
    }
};
 
typedef priority_queue<muchie *, vector<muchie *>, ComparatorMuchie> MinHeapMuchie;
 
class UF
{
    int *id;
    int *sz;
    int size;
    int comp;
     
    int find_id(int v);
     
public:
    UF(int size);
    ~UF();
    bool connected(int u, int v);
    void unify(int u, int v);
    int components() const { return comp; }
};
 
UF::UF(int size)
{
    this->size = size;
    comp = 0;
    id = new int[size];
    sz = new int[size];
     
    for(int i = 0; i < size; i++)
    {
        id[i] = i;
        sz[i] = 1;
    }
     
    comp = size;
}
 
UF::~UF()
{
    delete[] id;
    delete[] sz;
}
 
int UF::find_id(int v)
{
    // valideaza v
    int root = v;
    while(root != id[root])
        root = id[root];
    while(v != root)
    {
        int new_root = id[v];
        id[v] = root;
        v = new_root;
    }
     
    return root;
}
 
bool UF::connected(int u, int v)
{
    return find_id(u) == find_id(v);
}
 
void UF::unify(int u, int v)
{
    int root_u = find_id(u);
    int root_v = find_id(v);
     
    if (sz[root_u] < sz[root_v])
    {
        id[root_u] = root_v;
        sz[root_v] += sz[root_u];
    }
    else
    {
        id[root_v] = root_u;
        sz[root_u] += sz[root_v];
    }
     
    comp--;
}
 
 
class MinPQ
{
    muchie **pq;
    int capacity;
    int N;
     
    // array helper functions
    inline void exch(int i, int j);
    inline bool greater(int i, int j);
     
    // heap helper functions
    void swim(int k);
    void sink(int k);
     
public:
    MinPQ(int size);
    ~MinPQ();
    bool empty() { return N == 0; }
    void insert(muchie * key);
    muchie *min() { return pq[1]; }
    muchie *delMin();
};
 
MinPQ::MinPQ(int size)
{
    capacity = size+1;
    N = 0;
    pq = new muchie*[size+1];
}
 
MinPQ::~MinPQ()
{
    delete[] pq;
}
 
inline void MinPQ::exch(int i, int j)
{
    muchie *temp = pq[i];
    pq[i] = pq[j];
    pq[j] = temp;
}
 
inline bool MinPQ::greater(int i, int j)
{
    return pq[i]->cost > pq[j]->cost;
}
 
void MinPQ::swim(int k)
{
    while(k > 1 && greater(k/2, k))
    {
        exch(k/2, k);
        k = k/2;
    }
}
 
void MinPQ::sink(int k)
{
    while(2*k <= N)
    {
        int j = 2*k;
        if (j < N && greater(j, j+1)) j++;
        if (!greater(k, j)) break;
        exch(k ,j);
        k = j;
    }
}
 
void MinPQ::insert(muchie * key)
{
    pq[++N] = key;
    swim(N);
}
 
muchie *MinPQ::delMin()
{
    exch(1, N);
    muchie *min = pq[N--];
    sink(1);
    pq[N+1] = NULL;
    return min;
}
 
class Kruskal
{
public:
    void run(char *, char *);
};
 
void Kruskal::run(char *filename, char *output_filename)
{
    // Kruskal //
     
    ifstream in(filename);
     
     
    unsigned n,m;
    in >> n;
    in >> m;
     
    MinPQ q(m);
     
    for(unsigned i = 0; i < m; i++)
    {
        int origine, extremitate, cost;
        in >> origine >> extremitate >> cost;
        muchie *curent = new muchie(origine, extremitate, cost);
        curent->decr();
        q.insert(curent);
    }
     
    UF uf(n);
     
    int MSTcost = 0;
     
 
    queue<muchie *> MST;
     
    while(!q.empty() && MST.size() < m)
    {
        muchie *edge = q.delMin();
         
        int v = edge->start, w = edge->end;
         
        if (!uf.connected(v, w))
        {
            uf.unify(v, w);
             
             
            MST.push(edge);
             
            MSTcost += edge->getCost();
        }
    }
     
    // write data on output file and the exit
     
    ofstream out_file(output_filename);
     
    out_file << MSTcost << '\n';
    out_file << MST.size() << '\n';
     
    while(!MST.empty())
    {
        muchie *vf = MST.front();
        vf->incr();
        MST.pop();
        out_file << vf;
    }
     
     
    out_file.close();
}
 
int main(int argc, char **argv)
{
     
    Kruskal K;
    K.run("apm.in", "apm.out");
 
     
     
    return 0;
}