#include<fstream>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#define NMax 200005
#define MMax 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct Arc
{
    int x,y,c;
};

int N,M,Cost;
int TT[NMax],R[NMax];
Arc V[MMax];
vector <int> Sol;

bool Cmp(Arc a,Arc b)
{
    return (a.c < b.c);
}

void Read()
{
    fin>>N>>M;

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

    sort(V+1,V+M+1,Cmp);
}

int Father(int x)
{
    while(TT[x] != x)
        x = TT[x];

    return x;
}

void Unite(int x,int y)
{
    if(R[x] < R[y]) TT[x] = y;
    else    TT[y] = x;

    if(R[x] == R[y])    R[x]++;
}

void Solve()
{
    for(int i = 1 ; i <= N ; ++i)
        TT[i] = i;

    for(int i = 1 ; i <= M ; ++i)
    {
        int X = Father(V[i].x);
        int Y = Father(V[i].y);

        if(X != Y)
        {
            Unite(X,Y);
            Cost += V[i].c;
            Sol.push_back(i);
        }
    }
}

void Print()
{
    fout<<Cost<<"\n"<<N-1<<"\n";

    for(int i = 0 ; i < (int) Sol.size() ; ++i)
        fout<<V[Sol[i]].x<<" "<<V[Sol[i]].y<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();

    fin.close();
    fout.close();
    return 0;
}