#include <iostream>
#include <fstream>
#include <algorithm>
#define Nmax 200005
#define Mmax 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{
    int x,y,c;
};
muchie m[Mmax];
int N,M,R[Nmax],TT[Nmax],sol[Mmax],solc,k;
bool comp(muchie a, muchie b)
{
    return a.c<b.c;
}
void read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
        fin>>m[i].x>>m[i].y>>m[i].c;
    sort(m+1,m+M+1,comp);
}
void precalc()
{
    for(int i=1;i<=N;i++)
        TT[i]=i;
}
int father(int x)
{
    while(TT[x]!=x)
        x=TT[x];
    return x;
}
void unite(int x,int y)
{
    if(R[x]<R[y])
        TT[x]=y;
    if(R[x]>R[y])
        TT[y]=x;
    if(R[x]==R[y])
    {
        TT[x]=y;
        R[y]++;
    }
}
bool check(muchie a)
{
    int x=father(a.x);
    int y=father(a.y);
    if(x!=y)
    {
        unite(x,y);
        return 1;
    }
    return 0;
}
void solve()
{
    precalc();
    for(int i=1;i<=M;i++)
    {
        if(check(m[i]))
        {
            sol[++k]=i;
            solc+=m[i].c;
        }
    }
}
void print()
{
    fout<<solc<<"\n"<<k<<"\n";
    for(int i=1;i<=k;i++)
        fout<<m[sol[i]].x<<" "<<m[sol[i]].y<<"\n";
}
int main()
{
    read();
    solve();
    print();
    return 0;
}