#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <stack>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct graf{
int nod;
int dist;
graf* next;
};

struct Point{
int x;
int y;
int getX;
};

struct nod{
    int val;
    nod* next;
};

stack <Point> cache;

nod* v[200001];
int u1[200001];
int u2[200001];

graf* g[200001];

void add(int a, int b, int cost)
{
    graf* q = new graf;
    q->nod  = b;
    q->dist = cost;
    q->next = g[a];
    g[a] = q;
}

class myComparator
{
public:
    int operator() (const Point& p1, const Point& p2)
    {
        return p1.getX > p2.getX;
    }
};

void update(int a, nod *t){
    nod *p,*q;

    p = v[a];
    q = p;
    while(p->next!=NULL){
        q = p->next;
        p->next = t;
        p = q;
    }

    v[a] = t;
}

int k(int a){
    nod *p;
    for(p=v[a];p->next!=NULL;p=p->next);
    update(a,p);

    return p->val;
}





void connect(int a,int b){
    nod *p,*q,*t;
    int l2 = 0;
    int l1 = 0;

    for(p=v[a];p->next!=NULL;p=p->next)
        ++l1;
    for(q=v[b];q->next!=NULL;q=q->next)
        ++l2;

    if(l1 > l2)
        t = q->next = p;
    else
        t = p->next = q;

    update(a,t);

    update(b,t);

}

int main()
{
    int i,x,y,z;
    int n,m,s;
    Point P;
    priority_queue <Point, vector<Point>, myComparator> pq;
    fin >> n >> m ;
    for(i=1;i<=m;++i){
    fin >> x >> y >> z;
    add(x,y,z);
    add(y,x,z);
    P.x = x;
    P.y = y;
    P.getX = z;
    pq.push(P);
    }

    for(i=1;i<=n;++i){
        v[i] = new nod;
        v[i]->val = i;
        v[i]->next = NULL;
    }
    int a,b;
    int sum = 0;

    while (pq.empty() == false)
    {
        Point p = pq.top();
        a = p.x;
        b = p.y;
        if(k(a) != k(b)){
            connect(a,b);
            sum = sum + p.getX;
            cache.push(p);
        }
        pq.pop();
    }
    fout << sum << endl << n-1 << endl;
    while (cache.empty() == false){
        Point q = cache.top();
        fout << q.y << " " << q.x << "\n";
        cache.pop();
    }

    return 0;
}