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

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

struct muchie
{
    int x,y,cost;
}Graf[400010];
int N,M,Tata[200010],Ans,Sol[200010];

inline bool mycomp(const muchie &A,const muchie &B)
{
    return A.cost<B.cost;
}

int find(int nod)
{
    if(nod==Tata[nod])
        return nod;

    return (Tata[nod]=find(Tata[nod]));
}

int main()
{
    in>>N>>M;
    int i,Tx,Ty;
    for(i=1;i<=M;i++)
        in>>Graf[i].x>>Graf[i].y>>Graf[i].cost;

    for(i=1;i<=N;i++)
        Tata[i]=i;

    sort(Graf+1,Graf+M+1,mycomp);

    for(i=1;i<=M;i++)
    {
        Tx=find(Graf[i].x);
        Ty=find(Graf[i].y);

        if(Tx!=Ty)
        {
            Ans+=Graf[i].cost;
            Sol[++Sol[0]]=i;
            Tata[Tx]=Ty;
        }
    }

    out<<Ans<<"\n"<<Sol[0]<<"\n";
    for(i=1;i<=Sol[0];i++)
        out<<Graf[Sol[i]].x<<" "<<Graf[Sol[i]].y<<"\n";

    return 0;
}