#include<iostream>
#include<fstream>
#include<vector>
#define MIN_COST -1001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
struct vertex
{
    int cost;
    int x;
    int y;
};
struct special_vertex
{
    int x;
    int y;
};
vector<vertex> vec;
vector<int> disjoint;
vector<int> rang;
vector<special_vertex> vec2;
int heap_size;
void heapify(int pos)
{
    int c1 = 2*pos+1;
    int c2 = 2*pos+2;
    int maxx = MIN_COST;
    int maxx_pos;
    if(c1 <= heap_size)
    {
        if(vec[c1].cost > maxx) maxx = vec[c1].cost,maxx_pos=c1;
    }
    if(c2 <= heap_size)
    {
        if(vec[c2].cost > maxx) maxx = vec[c2].cost,maxx_pos=c2;
    }
    if(maxx > vec[pos].cost)
    {
        swap(vec[pos],vec[maxx_pos]);
        heapify(maxx_pos);
    }
}
void heap_sort()
{
    for(int i=heap_size/2;i>=0;i--)
    {
        heapify(i);
    }
    while(heap_size > 0)
    {
        swap(vec[0],vec[heap_size]);
        heap_size--;
        heapify(0);
    }
}
void print_heap()
{
    for(int i=0;i<vec.size();i++)
    {
        fout<<vec[i].cost<<" "<<vec[i].x<<" "<<vec[i].y<<"\n";
    }
    fout<<"\n";
}
void make_set(int x,int y)
{
    if(rang[x] > rang[y])
    {
        disjoint[y] = x;
    }
    else disjoint[x] = y;
    if(rang[x] == rang[y]) rang[y]++;
}
int cross(int x)
{
    if(disjoint[x] == x) return disjoint[x];
    disjoint[x] = cross(disjoint[x]);
    return disjoint[x];
}
int main()
{
    fin>>n>>m;
    int k1,k2,k3;
    for(int i=0;i<m;i++)
    {
        fin>>k1>>k2>>k3;
        vertex b;
        b.cost = k3;
        b.x = k1;
        b.y = k2;
        vec.push_back(b);
        disjoint.push_back(i);
        rang.push_back(1);
    }
    if(n > m)
    {
        for(int i=m;i<n;i++)
        {
            disjoint.push_back(i);
            rang.push_back(1);
        }
    }
    heap_size = vec.size()-1;
    heap_sort();
    int s = 0;
    int nn = 0;
    for(int i=0;i<vec.size();i++)
    {
        if(cross(vec[i].x-1) != cross(vec[i].y-1))
        {
            make_set(cross(vec[i].x-1),cross(vec[i].y-1));
            s += vec[i].cost;
            special_vertex v;
            v.x = vec[i].x;
            v.y = vec[i].y;
            vec2.push_back(v);
            nn++;
        }
    }
    fout<<s<<"\n"<<nn<<"\n";
    for(int i=0;i<vec2.size();i++)
    {
        fout<<vec2[i].y<<" "<<vec2[i].x<<"\n";
    }
}