#include<bits/stdc++.h>
#define maxtata 200005
#define maxV 450000

using namespace std;

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

int n,m,tata[maxtata];

struct Edge
{
    int x,y,cost;
}V[maxV];

bool compara(Edge a,Edge b)
{
    return a.cost<b.cost;
}

int BigDaddy(int nod)
{
    if(tata[nod]==0)
        return nod;
    return BigDaddy(tata[nod]);
}

void unim(int A,int B)
{
    if(A==B)
        return;
    tata[B]=A;
    unim(A,tata[B]);
}

int main()
{
    int cost_minim=0;
    int sol[maxV],k=0;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>V[i].x>>V[i].y>>V[i].cost;
    sort(V+1,V+m+1,compara);
    for(int i=1;i<=m;i++)
    {
        int tata_x=BigDaddy(V[i].x);
        int tata_y=BigDaddy(V[i].y);
        if(tata_x!=tata_y) //daca e ok
        {
            cost_minim+=V[i].cost;
            sol[++k]=i;
            tata[tata_y]=tata_x;
            unim(tata_x,V[i].y);
        }
    }
    fout<<cost_minim<<"\n"<<n-1<<"\n";
    for(int i=1;i<=k;i++)
    {
        fout<<V[sol[i]].y<<" "<<V[sol[i]].x<<"\n";
    }
    return 0;
}