#define nume "apm"

#include<cstdio>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<string>
#include<sstream>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<list>
#include<algorithm>

using namespace std;

#ifdef _PARSARE_
//////////////////////////////////////////////////////////////
//parsarea citirii
//////////////////////////////////////////////////////////////
#define DIM 8192
char ax[DIM+16];
int idx;

//numere NATURALE:
inline void cit_uint(int &x)
{
    x=0;
    while(ax[idx]<'0' || ax[idx]>'9')
        if(++idx==DIM)fread(ax, 1, DIM, stdin), idx=0;
    while(ax[idx]>='0' && ax[idx]<='9') {
        x=x*10+ax[idx]-'0';
        if(++idx==DIM)fread(ax,1, DIM, stdin),idx=0;
    }
}

//numere INTREGI:
inline void cit_int(int &x)
{
    x=0;
    while((ax[idx]<'0' || ax[idx]>'9') && (ax[idx]!='-'))
        if(++idx==DIM)fread(ax, 1, DIM, stdin), idx=0;

    int neg=0;
    if(ax[idx]=='-') {
        neg=1;
        if(++idx==DIM)fread(ax, 1, DIM, stdin),idx=0;
    }

    while(ax[idx]>='0' && ax[idx]<='9') {
        x=x*10+ax[idx]-'0';
        if(++idx==DIM)fread(ax,1, DIM, stdin),idx=0;
    }
    if(neg) x=-x;
}
#else
ifstream fin (nume  ".in");
#endif //_PARSARE_
ofstream fout(nume  ".out");
//#ifndef ONLINE_JUDGE
//	freopen("input.txt","r",stdin);
//#endif


int n;
vector<int> G;
struct edge {
    int x,y,c;
};
edge E[400000+10];
bool cmp(edge a, edge b)
{
    return a.c<b.c;
}
int root[200000+10];
inline int find(int x)
{
    int r=x;
    while(r!=root[r])
        r=root[r];
    while(x!=root[x]){
        int tmp=root[x];
        root[x]=r;
        x=tmp;
    }
    return r;
}
inline void join(int x,int y)
{
    x=find(x);
    y=find(y);
    
    if(rand()%2)
        root[x]=y;
    else
        root[y]=x;
}
int main()
{
#ifdef _PARSARE_
    freopen(nume  ".in","r",stdin);
    cit_uint(n);
#endif
    int n,m;
    fin>>n>>m;

    for(int i=0; i<m; ++i) {
        fin>>E[i].x>>E[i].y>>E[i].c;
    }

    sort(E,E+m,cmp);
    
    for(int i=1;i<=n;++i){
        root[i]=i;
    }
    long long cost=0;
    for(int i=0; i<m; ++i) {
        if(find(E[i].x)!=find(E[i].y)) {
            join(E[i].x,E[i].y);
            cost+=E[i].c;
            G.push_back(i);
        }
    }
    fout<<cost<<'\n';
    fout<<G.size()<<'\n';
    for(int i=0;i<G.size();++i)
        fout<<E[G[i]].x<<' '<<E[G[i]].y<<'\n';

    fout.close();
    return 0;
}