#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
vector<pair<int,pair<int,int>> >gr;
vector<pair<int,int>>ras;
int t[200002],cost,n,m;
int radacina(int nod)
{
    if(nod==t[nod])
        return t[nod];
    t[nod]=radacina(t[nod]);
    return t[nod];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        t[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        gr.push_back(make_pair(c,make_pair(x,y)));
    }
    sort(gr.begin(),gr.end());
    for(int i=0;i<gr.size();i++)
    {
        int ra=radacina(gr[i].second.first);
        int rb=radacina(gr[i].second.second);
        if(ra!=rb)
        {
            ras.push_back(make_pair(gr[i].second.second,gr[i].second.first));
            t[ra]=rb;
            cost+=gr[i].first;
        }
    }
    cout<<cost<<'\n';
    cout<<ras.size()<<'\n';
    for(int i=0;i<ras.size();i++)
        cout<<ras[i].first<<' '<<ras[i].second<<'\n';
}