#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct Edge
{
    int x,y,w;

    bool operator < (const Edge& e) const
    {
        return w<e.w;
    }
};

int N,M;
vector<Edge> G;
vector<int> father, h;
int cost_min;
vector<Edge> apm;
int cnt; ///nr de muchii in apm

void Union(int x,int y);
int Find(int x);
void Kruskal();
void Read();

int main()
{
    Read();
    Kruskal();

    fout<<cost_min<<'\n';
    fout<<cnt<<'\n';

    for(const Edge& e : apm)
        fout<<e.x<<" "<<e.y<<'\n';

    fout.close();
    return 0;
}

void Union(int x,int y)
{
    if(h[y]>h[x])
        father[x]=y;

    else
    {
        father[y]=x;

        if(h[x]==h[y])
            h[x]++;
    }
}
int Find(int x)
{
    if(x==father[x]) return x;
    return father[x]=Find(father[x]);
}
void Kruskal()
{
    sort(G.begin(),G.end());
    int c1, c2;

    for(const Edge& e : G)
    {
        c1=Find(e.x);
        c2=Find(e.y);

        if(c1!=c2)
        {
            cost_min+=e.w;
            apm.push_back(e);
            Union(c1,c2);
            ++cnt;

            if(cnt==N-1) break;
        }
    }
}
void Read()
{
    fin>>N>>M;
    father=vector<int>(N+1);
    h=vector<int>(N+1);

    for(int i=1;i<=N;++i)
        father[i]=i,h[i]=0;
    while(M--)
    {
        int x,y,z;
        fin>>x>>y>>z;
        G.push_back({x,y,z});
    }
    fin.close();
}