#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

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

int n,m;
int tata[200005];
int rang[200005];
int costTotal;

vector<pair<int,int > > sol;

struct muchie
{
    int x,y,c;
}v[400005];

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].c;
    }
}

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

int Find(int nod)
{
    while(tata[nod]!=nod)
        nod=tata[nod];
    return nod;
}

void Unite(int x,int y)
{
    if(rang[x]<rang[y])
        tata[x]=y;
    if(rang[y]<rang[x])
        tata[y]=x;
    if(rang[x]==rang[y])
    {
        tata[x]=y;
        rang[y]++;
    }
}

int main()
{
    citire();
    for(int i=1;i<=m;i++)
    {
        tata[i]=i;
        rang[i]=1;
    }
    sort(v+1,v+m+1,compara);
    for(int i=1;i<=m;i++)
    {
        if(Find(v[i].x)!=Find(v[i].y))
        {
            Unite(Find(v[i].x),Find(v[i].y));
            sol.push_back({v[i].y,v[i].x});
            costTotal+=v[i].c;
        }
    }
    fout<<costTotal<<"\n";
    fout<<n-1<<"\n";
    for(int i=0;i<sol.size();i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
    return 0;
}