#include <iostream>
#include <vector>
#include <utility>
#include <fstream>
#include <limits.h>

using namespace std;

vector<pair<int,int> > *a;
pair<int,int> *p;
int *viz,c=0,cost=0;

void getree(int x) {
    int maxim = INT_MAX,y,is = 0;
    viz[x] = 1;
    unsigned int s = a[x].size(),i;
    while (is != -2) {
        is = -2;
        for (i=0;i<s;i++) {
            y = a[x][i].second;
            if (y <= maxim && !viz[a[x][i].first]) {
                maxim = y;
                y = 0;
                is = i;
            }

        }
        if (is != -2) {
            cost += maxim;
            p[c] = make_pair(x,a[x][is].first);
            c++;
            getree(a[x][is].first);
        }
    }
}



int main()
{
    ifstream f("apm.in");
    int n,m,x,y,co,i;
    f>>n;
    f>>m;
    a = new vector<pair<int,int> >[n+1];
    p = new pair<int,int>[n];
    viz = new int[n+1];
    for (i=1;i<=n;i++) viz[i] = 0;
    while (f>>x>>y>>co)
        a[x].push_back(make_pair(y,co));
    f.close();
    getree(1);
    ofstream g("apm.out");
    g<<cost;
    g<<endl<<c;
    g<<endl;
    for (i=0;i<n-1;i++) g<<p[i].first<<" "<<p[i].second<<endl;
    return 0;
}