#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector<int> tata;
vector<pair<pair<int,int>,int>> K,lf;
int Find(int x)
{
     if(x==tata[x])
        return x;
     tata[x]=Find(tata[x]);
       return tata[x];
}
bool cmp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b)
{
    return a.second<b.second;
}
void Union(int x,int y)
{
    int a=Find(x);
    int b=Find(y);
    tata[a]=b;
}
int main()
{
    long long n,m,i,a,b,c;
    f>>n>>m;
    tata.resize(n+1);
    for(i=1;i<=n;i++)
        tata[i]=i;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        K.push_back({{a,b,},c});
    }
    sort(K.begin(),K.end(),cmp);
    i=0;
    long long int cost=0,nr=0;
    while(nr!=n-1)
    {
        if(Find(K[i].first.first)!=Find(K[i].first.second))
        {
            nr++;
            cost+=K[i].second;
            lf.push_back({{K[i].first.first,K[i].first.second},K[i].second});
            Union(K[i].first.first,K[i].first.second);

        }
        i++;
    }
    g<<cost<<endl<<nr<<endl;
    for(i=0;i<nr;i++)
        g<<lf[i].first.second<<" "<<lf[i].first.first<<endl;
}