#include<cstdio>
#include<algorithm>
#include<vector>

#define pb push_back
#define mp make_pair
#define N_MAX 200010
using namespace std;

struct muchie {int x,y,c;};

vector <muchie> G;
vector < pair<int,int> > Sol;
vector <muchie> :: iterator it;

int rang[N_MAX],T[N_MAX],Cost_Total=0;

inline void Write_Data()
{
    vector < pair<int,int> > :: iterator it;
    printf("%d\n%d\n",Cost_Total,Sol.size());
    for (it=Sol.begin();it!=Sol.end();++it)
        printf("%d %d\n",(*it).first,(*it).second);
}

inline bool cmp(muchie a,muchie b){ return (a.c<b.c);}

inline void Reunit(int x,int y)
{
    if (rang[x]<rang[y]) T[x]=y;
        else T[y]=x;
    if (rang[x]==rang[y]) rang[x]++;
}

inline int Multime (int x)
{
    if (T[x]!=x) T[x]=Multime(T[x]);
    return T[x];
}

inline void Load_Data()
{
    int N,M,i;
    muchie nr;
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;i++)
        scanf("%d%d%d",&nr.x,&nr.y,&nr.c), G.pb(nr);
    for (i=1;i<=N;i++)
        T[i]=i, rang[i]=0;
    sort(G.begin(),G.end(),cmp);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    Load_Data();
    for (it=G.begin();it!=G.end();++it)
    {
        muchie NR=*it;
        int i=NR.x,j=NR.y,k=NR.c;
        int a=Multime(i),b=Multime(j);
        if (a!=b)
            {
                Reunit(a,b);
                Cost_Total+=k;
                Sol.pb(mp(i,j));
            }
    }
    Write_Data();
    fclose(stdin);
    fclose(stdout);
    return 0;
}