#include<bits/stdc++.h>
using namespace std;

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

struct muchie{int x, y, c;}v[400005];
int tata[200005], h[200005], viz[400005], ct;
int s, n, m, i;

inline bool cmp(muchie A, muchie B)
    {return A.c < B.c;}
int Find_dad(int q)
{
    while(tata[q] != q)
        q = tata[q];
    return tata[q];
}
void Union(int p, int q)
{
    if(h[Find_dad(p)] < h[Find_dad(q)])
    {
        tata[Find_dad(p)] = tata[Find_dad(q)];
    }
    else{tata[Find_dad(q)] = tata[Find_dad(p)];
        if(h[p] == h[q]) h[p] ++;
    }
}

int main()
{
    fin>>n>>m;
    for(i = 1; i <= n; i++)
        {tata[i] = i; h[i] = 1;}
    for(i = 1; i <= m; i++)
        fin>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1, v+m+1, cmp);
    for(i = 1; i <= m; i++)
    {
        if(Find_dad(v[i].x) != Find_dad(v[i].y))
        {
            s += v[i].c;
            Union(v[i].x, v[i].y); viz[i] = 1; ct++;
            if(ct == n-1) break;
        }
    }
    fout<<s<<"\n"<<n-1<<"\n";
    for(i = 1; i <= m; i++)
    {
        if(viz[i] == 1) fout<<v[i].x<<" "<<v[i].y<<"\n";
    }

    return 0;
}