using namespace std;
#include<fstream>
#include<algorithm>

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

#define Nmax 400005

pair <int,int> P[Nmax];

int N,M,cost,TT[Nmax],k,RG[Nmax];

struct Muchie
{
    int x,y,cost;

};
Muchie E[Nmax];
int CMP(Muchie A,Muchie B)
{
    return A.cost<B.cost;
}

void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
        fin>>E[i].x>>E[i].y>>E[i].cost;
    sort(E+1,E+M+1,CMP);
}

int Father(int x)
{
    while(TT[x]!=x)
        x=TT[x];
    return x;
}

void Unite(int x,int y)
{
    if(RG[x]<RG[y])
        TT[x]=y;
    if(RG[y]<RG[x])
        TT[y]=x;
    if(RG[x]==RG[y])
        TT[x]=y,RG[y]++;
}
void Solve()
{
    for(int i=1;i<=M;i++)
        if(Father(E[i].x)!=Father(E[i].y))
        {
            int a=E[i].x,b=E[i].y,c=E[i].cost;
            Unite(Father(a),Father(b));
            P[++k].first=a;
            P[k].second=b;
            cost+=c;
        }
}

int main()
{
    Read();
    for(int i=1;i<=M;i++)
        TT[i]=i,RG[i]=1;
    Solve();
    fout<<cost<<"\n";
    fout<<N-1<<"\n";
    for(int i=1;i<=k;i++)
        fout<<P[i].second<<" "<<P[i].first<<"\n";
    return 0;
}