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

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

const int NMAX = 1e5;

struct edge
{
    int x,y,c;
};
int n,m;
int tata[NMAX+5],d[NMAX+5];
vector<edge> edges;
vector<edge> ans;

bool cmp(edge a, edge b)
{
    return a.c<b.c;
}

int find(int node)
{
    int r=tata[node];
    while(tata[r]!=r)
    {
        r=tata[r];
    }
    return r;
}

void join(int r1, int r2)
{
    if(d[r1]==d[r2])
    {
        tata[r1]=r2;
        d[r2]++;
    }
    else if(d[r1]<d[r2]) tata[r1]=r2;
    else tata[r2]=r1;
}
int main()
{
    in>>n>>m;
    for(int i=1; i<=n; i++)
        tata[i]=i,d[i]=1;

    for(int i=1; i<=m; i++)
    {
        edge aux;
        in>>aux.x>>aux.y>>aux.c;
        edges.push_back(aux);
    }

    sort(edges.begin(),edges.end(),cmp);

    int cost=0;
    for(auto it:edges)
    {
        int r1=find(it.x);
        int r2=find(it.y);
        if(r1 != r2)
        {
            cost+=it.c;
            join(r1,r2);
            ans.push_back(it);
        }
    }

    out<<cost<<'\n'<<ans.size()<<'\n';
    for(auto it:ans)
        out<<it.y<<' '<<it.x<<'\n';

    return 0;
}