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

using namespace std;

struct muchie
{
    int a,b,cost;
};

muchie v[400002];
int to[200002],rang[200002];
vector < pair < int , int > > ans;

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

inline int find(int x)
{
    int R=x;
    while(to[R]!=R)
        R=to[R];
    while(to[x]!=x)
    {
        int y=to[x];
        to[x]=R;
        x=y;
    }
    return R;
}

inline void unite(int x, int y)
{
    if(rang[x]>rang[y])
        to[y]=x;
    else
        to[x]=y;
    if(rang[x]==rang[y])
        rang[y]++;
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n,m; f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>v[i].a>>v[i].b>>v[i].cost;
    sort(v+1,v+m+1,cmp);

    for(int i=1;i<=n;i++)
    {
        rang[i]=1;
        to[i]=i;
    }

    int cost=0;
    for(int i=1;i<=m;i++)
    {
        if(find(v[i].a)!=find(v[i].b))
        {
            unite(find(v[i].a), find(v[i].b));
            cost+=v[i].cost;
            ans.push_back({v[i].a, v[i].b});
        }
    }

    g<<cost<<'\n'<<ans.size()<<'\n';
    for(auto x: ans)
        g<<x.first<<" "<<x.second<<'\n';
    f.close();
    g.close();
    return 0;
}