#include <bits/stdc++.h>
#define N 200005
#define M 2*N
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct muchie{
    int x,y,val;
};
muchie lista[M];
stack<muchie>sol;
int n,m,dad[N],nr,cost;

bool cmp(muchie st,muchie dr)
{
    return st.val<dr.val;
}
int big_D(int node)
{
    int rez=node;
    while(dad[rez]!=rez) rez=dad[rez];
    while(dad[node]!=node)
    {
        int cpy=dad[node];
        dad[node]=rez;
        node=cpy;
    }
    return rez;
}
void citire()
{
    in>>n>>m;
    for(int i=1;i<=n;i++) dad[i]=i;
    for(int i=1;i<=m;i++) in>>lista[i].x>>lista[i].y>>lista[i].val;
}
void solv()
{
    sort(lista+1,lista+m+1,cmp);
    for(int i=1;i<=m && nr<n-1;i++)
    {
        if(big_D(lista[i].x)==big_D(lista[i].y)) continue;
        dad[lista[i].x]=big_D(lista[i].y);
        nr++;
        cost+=lista[i].val;
        sol.push(lista[i]);
    }
    out<<cost<<'\n'<<nr<<'\n';
    while(!sol.empty())
    {
        out<<sol.top().x<<' '<<sol.top().y<<'\n';
        sol.pop();
    }
}
int main()
{
    citire();
    solv();
    return 0;
}