#include <fstream>
#include <queue>
#define NMAX 400004

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

struct muchie
{

    int x,y,c;
    friend bool operator >(const muchie &a, const muchie &b);
};

bool operator >(const muchie &a, const muchie &b)
{
    return a.c>b.c;
}

int tata[NMAX],h[NMAX];
int n, m;
priority_queue< muchie, vector<muchie>, greater<muchie> >H;
vector<muchie> v;

int Find(int x)
{
    int rx=x,y;
    while(tata[rx]) rx=tata[rx];
    while(x!=rx)
    {
        y=tata[x];
        tata[x]=rx;
        x=y;
    }
    return rx;
}

void Union(int x, int y)
{
    if(h[x]>h[y])
        tata[y]=x;
    else if(h[x]<h[y])
        tata[x]=y;
    else
    {
        tata[y]=x;
        h[x]++;
    }
}
void kruskal()
{
    int nrsel=0,s=0,rx,ry;
    muchie srt;
    while(nrsel<n-1)
    {
        srt=H.top();
        H.pop();
        rx=Find(srt.x);
        ry=Find(srt.y);
        if(rx!=ry)
        {
            Union(rx,ry);
            v.push_back(srt);
            nrsel++;
            s+=srt.c;
        }
    }
    fout<<s<<'\n'<<nrsel<<'\n';
    for(int i=0; i<nrsel; i++)
        fout<<v[i].y<<' '<<v[i].x<<'\n';
}
int main()
{
    fin>>n>>m;
    muchie srt;
    for(int i=1; i<=m; i++)
    {
        fin>>srt.x>>srt.y>>srt.c;
        H.push(srt);
    }
    kruskal();
    return 0;
}
/*#include <fstream>
#include <cstdio>
#include <algorithm>
#define NMAX 200005
#define MMAX 400010

using namespace std;

FILE*fin;
ofstream fout("apm.out");

struct muchie{
int x, y, cost;
} v[NMAX];

int n, m, h[NMAX], tata[NMAX], sol[NMAX],cost;
void citire();
void kruskal();
int Find(int x);
void Union(int x, int y);
void afisare();

int criteriu(muchie A, muchie B)
{
    if(A.cost > B.cost)
        return 0;
    return 1;
}

int main()
{
    citire();
    sort(v + 1, v + n + 1, criteriu);
    kruskal();
    afisare();
    return 0;
}

void citire()
{
    int i;
    fin = freopen("apm.in", "r", stdin);
    fscanf(fin, "%d%d", &n, &m);
    for(i = 1; i <= m; i++)
        fscanf(fin, "%d%d%d", &v[i].x, &v[i].y, &v[i].cost);
}

void kruskal()
{
    int i, nrsel = 0, adv = 0, rx, ry, nrsol = 0;
    muchie p;
    while(nrsel < n - 1)
    {
        ++adv;
        p = v[adv];
        rx = Find(p.x);
        ry = Find(p.y);
        if(rx != ry)
        {
            Union(rx, ry);
            sol[++nrsol] = adv;
            cost += p.cost;
            ++nrsel;
        }
    }

}

int Find(int x)
{
    int rx = x, y;
    while(tata[rx]) rx = tata[rx];
    while(x != rx)
    {
        y = tata[x];
        tata[x] = rx;
        x = y;
    }
    return x;
}

void Union(int x, int y)
{
    if(h[x] > h[y])
    {
        tata[y] = x;
    }
    else if(h[x] < h[y])
    {
        tata[x] = y;
    }
        else{
            tata[y] = x;
            h[x]++;
        }
}

void afisare()
{
    int i;
    fout << cost << '\n';
    fout << n - 1 << '\n';
    for(i = 1; i <= n - 1; i++)
        fout << v[sol[i]].x << ' '<< v[sol[i]].y << '\n';
}
*/