#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,cost_final,parent[200005],h[200005];
vector<pair<int,int>>ans;

struct Edge{
    int first,second,third;
}e[200005];

bool comp(Edge a, Edge b){
    return a.third<b.third;
}

int Find(int a)
{
    if(parent[a]==a)return a;
    return parent[a]=Find(parent[a]);
}

bool Union(int a, int b)
{
    a=Find(a);
    b=Find(b);

    if(a==b)return 0;
    else if(h[a]<h[b])parent[a]=b;
    else if(h[b]<h[a])parent[b]=a;
    else if(h[a]==h[b]){h[b]++;parent[a]=b;}
    return 1;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>e[i].first>>e[i].second>>e[i].third;
    }
    for(int i=1;i<=n;i++){
        h[i]=0;parent[i]=i;
    }
    sort(e+1,e+m+1,comp);
    for(int i=1;i<=m;i++)
    {
        if(Union(e[i].first,e[i].second))
        {
            cost_final+=e[i].third;
            ans.push_back(make_pair(e[i].first,e[i].second));
        }
    }
    fout<<cost_final<<'\n';
    fout<<ans.size()<<'\n';
    for(auto i:ans)
        fout<<i.first<<' '<<i.second<<'\n';
    return 0;
}