#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 200005;

struct apm
{
    int x;
    int y;
    int cost;
};

apm v[NMAX];
int parent[NMAX];
vector<int> R;

bool cmp(apm x,apm y)
{
    return ( x.cost < y.cost );
}

int get_root(int node)
{
    if(parent[node]<0) return node;
    int aux=node;
    while(parent[node]>0)
    {
        node=parent[node];
    }
    int root=node;
    node=aux;
    while(node!=root)
    {
        aux=parent[node];
        parent[node]=root;
        node=aux;
    }
    return root;
}

void unesc(int x,int y)
{
    int a=get_root(x);
    int b=get_root(y);
    if(a==b) return;
    if(parent[a]*(-1)>parent[b]*(-1))
    {
        parent[a]+=parent[b];
        parent[b]=a;
    }
    else
    {
        parent[b]+=parent[a];
        parent[a]=b;
    }
}

int main()
{
    int n,m;
    fin >> n >> m;
    apm nr;
    for(int i=1;i<=m;i++)
    {
        fin >> nr.x >> nr.y >> nr.cost;
        v[i]=nr;
        parent[nr.x]=-1;
        parent[nr.y]=-1;
    }
    sort(v+1,v+m+1,cmp);
    int rasp=0;
    for(int i=1;i<=m;i++)
    {
        if(parent[v[i].x]!=parent[v[i].y] or parent[v[i].x]<0 or parent[v[i].y]<0)
        {
            int a=get_root(v[i].x);
            int b=get_root(v[i].y);
            if(a==b) continue;
            rasp+=v[i].cost;
            unesc(a,b);
            R.push_back(i);
        }
    }
    fout << rasp << '\n';
    fout << n-1 << '\n';
    for(int i=0;i<R.size();i++)
    {
        fout << v[R[i]].y << ' ' << v[R[i]].x << '\n';
    }
    return 0;
}