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

int cost[nmax],n1[nmax], n2[nmax];
int IND[nmax];//pt sortare
int R[200007], L[200007]; //pt componentele conexe- R =rangul
int N,M;
bool arbore[nmax];

bool cmp(int x, int y)
{
    return cost[x] < cost[y];
}
int find(int x)
{
    int i = x , j = x;
    for(; i!= L[i] ; i = L[i]);

    do
    {
        int aux = j;
        j = L[j];
        L[aux] = i;

    }while(L[j] != j);

    return i;
}
void reunion(int x,int y)
{
    if(R[x] > R[y])
    {
        L[y] = x;
        R[y]++;

    }
    else{
    L[x] = y;
    R[x]++;
    }
}

void afis()
{
    for(int i = 1; i <= M; i++)
    if(arbore[i] == true)
        fout << n1[i] <<" " <<n2[i] <<'\n';


}

void Kruskal()
{
    int Cost_total = 0, NrM = 0;

    for(int i = 1; i <= N; i++)
        R[i] = 1, L[i] = i;

    for(int i = 1; i <= M ;i++)
    {
        int t1 = find(n1[IND[i]]) ;
        int t2 = find(n2[IND[i]]) ;
        if(t1 != t2){
            reunion(t1, t2);
            NrM++;
            arbore[IND[i]] = true;
            Cost_total += cost[IND[i]];
            if(NrM == N - 1)
            {
                fout <<Cost_total  <<'\n' << NrM <<'\n';
                afis();
                break;
            }
        }

    }
}
void read()
{
    fin >>N>>M;
    for(int i = 1; i <= M; i++)
    {
        fin >> n1[i] >> n2[i] >> cost[i];
        IND[i] = i;
    }
    sort(IND + 1, IND + 1 + M, cmp);
}

int main()
{
    read();
    Kruskal();

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