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

using namespace std;

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

muchie v[400000];
int to[200000],rang[200000];
vector<pair<int, int>>ans;

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

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

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,compare);


    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;
}