#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
#define Ndim 100005
#define Mdim 400005

int N,M,Cost=0;
int P[Ndim];
int h[Ndim];

vector<int> Muchii;

int root(int x){
    if(P[x] != x) P[x] = root(P[x]);
    return P[x];
}

void unite(int x,int y)
{
    int Rx = root(x);
    int Ry = root(y);

    if(h[Rx] > h[Ry]){
        P[Ry] = Rx;
        h[Rx] += h[Ry];
    }
    else{
        P[Rx] = Ry;
        h[Ry] += h[Rx];
    }
}

struct Muchie{
    int x,y,cost;
};

Muchie A[Mdim];

struct comp{
    bool operator()(const Muchie& a,const Muchie& b){
        return a.cost < b.cost;
    }
};

void Kruskal()
{
    for(int i = 1; i <= N; i++)
        P[i] = i, h[i] = 1;

    sort(A+1,A+M+1,comp());

    for(int i = 1; i <= M; i++)
        if(root(A[i].x) != root(A[i].y)){
            unite(A[i].x,A[i].y);
            Cost += A[i].cost;
            Muchii.push_back(i);
        }
}

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

    fin >> N >> M;

    for(int i = 1; i <= M; i++)
        fin >> A[i].x >> A[i].y >> A[i].cost;

    Kruskal();

    fout << Cost << "\n" << Muchii.size() << "\n";

    for(auto p: Muchii)
        fout << A[p].x << " " << A[p].y << "\n";
}