#include<bits/stdc++.h>
using namespace std;

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

int n,m;
int total,k;

const int maxn=400005;

int tata[maxn],rang[maxn];

struct muchie
{
    int x,y,cost;
}V[maxn];

bool compare(muchie a,muchie b)
{
    return a.cost < b.cost;
}

pair<int,int> sol[maxn];

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

    //sortam muchiile
    sort(V+1,V+m+1,compare);
}


//gasim tatal suprem
int Find(int nod)
{
    while(tata[nod]!=nod)
        nod=tata[nod];
    return nod;
}

//unim arborii mai mici de arborii mai mari
void unim(int x,int y)
{
    if(rang[x]<rang[y])
        tata[x]=y;
    else
        if(rang[x]>rang[y])
            tata[x]=y;
        else{
            tata[x]=y;
            rang[y]++;
        }
}

void solve()
{
    for(int i=1;i<=m;i++)
    {
        if(Find(V[i].x) != Find(V[i].y))
        {
            unim(Find(V[i].x),Find(V[i].y));
            sol[++k].first=V[i].x;
            sol[k].second=V[i].y;
            total+=V[i].cost;
        }
    }
}


int main()
{
    citire();
    for(int i=1;i<=m;i++)
    {
        tata[i]=i;
        rang[i]=1;
    }
    solve();
    fout<<total<<"\n";
    fout<<n-1<<"\n";
    for(int i=1;i<=k;i++)
    {
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
    }
    return 0;
}