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

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
typedef pair<int,pair<int,int>> xyz;
vector <xyz> e;
vector <pair<int,int>> rez;
int x,y,n,m,i,c,t[200005],cost,rang[200005];
int reprezentant(int x)
{
    if(t[x]!=x)
        t[x]=reprezentant(t[x]);
    return t[x];
}
void reuneste(int x,int y)
{
    x=reprezentant(x);
    y=reprezentant(y);
    if(rang[x]<rang[y]){
        t[x]=y;
        rang[y]+=rang[x];
        rang[x]=0;
    }
    else{
        t[y]=x;
        rang[x]+=rang[y];
        rang[y]=0;
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        e.push_back({c,{x,y}});
    }
    for(i=1;i<=n;i++)
        t[i]=i,rang[i]=1;
    sort(e.begin(),e.end());
 //   for(auto it : e)
   //     cerr << it.first << ' ' << it.second.first << ' ' << it.second.second << '\n';
    for(auto it : e)
    {
        x=it.second.first;
        y=it.second.second;
        c=it.first;
        if(reprezentant(x)!=reprezentant(y))
        {
            reuneste(x,y);
            cost+=c;
            rez.push_back({x,y});
        }
    }
    g<<cost<<'\n'<<rez.size()<<'\n';
    for(auto it : rez)
        g<<it.first<<' '<<it.second<<'\n';
    return 0;
}