#include <bits/stdc++.h>

using namespace std;

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

int TT[400001], grade[400001];
int n, m, muchii, SolSum;
vector<pair<int, int>>SOL;

struct Edge
{
    int x, y, c;
    bool operator <(const Edge &aux)const
    {
        return c<aux.c;
    }
};

Edge E[400001];

int root(int x)
{
    int R=x, y;
    while(R!=TT[R]) R=TT[R];
    while(x!=TT[x])
    {
        y=x;
        TT[x]=R;
        x=TT[y];
    }
    return R;
}

void unite(int x, int y)
{
    if(grade[x]>grade[y]) TT[y]=x;
    else TT[x]=y;
    if(grade[x]==grade[y]) ++grade[y];
}

void KRUSKAL()
{
    sort(E+1, E+m+1);

    for(int i=1; i<=m; ++i)
    {
        TT[i]=i;
        grade[i]=1;
    }

    for(int i=1; i<=m; ++i)
    {
        if(root(E[i].x)!=root(E[i].y))
        {
            SolSum=SolSum+E[i].c;
            ++muchii;
            SOL.push_back(make_pair(E[i].x, E[i].y));
            unite(root(E[i].x), root(E[i].y));
        }
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        fin>>E[i].x>>E[i].y>>E[i].c;
    }
    KRUSKAL();
    fout<<SolSum<<"\n"<<muchii<<"\n";
    for(auto it:SOL) fout<<it.first<<" "<<it.second<<"\n";
    return 0;
}