#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int M_MAX=4*1e5;
const int N_MAX=2*1e5;

struct Edge{
    int x;
    int y;
    int cost;
    bool used;
};

vector <Edge> edges;

bool cmp(const Edge &a, const Edge &b){
    return a.cost<b.cost;
}

int father[N_MAX+1];

int get_lead(int x){
    int leader=x,aux;
    while(leader!=father[leader])
        leader=father[leader];

    while(x!=father[x])
    {
        aux=x;
        x=father[x];
        father[aux]=leader;
    }
    return leader;
}

bool unite(int x,int y){
    x=get_lead(x);
    y=get_lead(y);

    if(x==y)
        return 0;

    father[y]=x;
    return 1;
}

int main()
{
    int n,m;
    fin>>n>>m;

    Edge aux;
    aux.used=0;
    for(int i=1;i<=m;i++)
    {
        fin>>aux.x>>aux.y>>aux.cost;
        edges.push_back(aux);
    }
    sort(edges.begin(),edges.end(),cmp);

    /*for(const Edge &e:edges)
        fout<<e.x<<" "<<e.y<<" "<<e.cost<<"\n";*/

    for(int i=1;i<=n;i++)
        father[i]=i;

    int total_cost=0;
    int x,y,cost;
    for(int i=0;i<m;i++)
    {
        x=edges[i].x;
        y=edges[i].y;
        cost=edges[i].cost;
        edges[i].used=unite(x,y);
        if(edges[i].used==1)
            total_cost+=cost;
    }

    fout<<total_cost<<"\n"<<n-1<<"\n";
    for(int i=0;i<m;i++)
        if(edges[i].used==1)
            fout<<edges[i].x<<" "<<edges[i].y<<"\n";

    return 0;
}