#include<algorithm>
#include<vector>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int maxn = 400100;

int GR[maxn],x,y,c;
int N,M,ANS,IND[maxn];
std::vector < pair <int ,pair <int , int > > > VANS;
std::vector < pair <int , int> > VANSout;

int grupa(int i)
{
    if (GR[i] == i) return i;
    GR[i] = grupa(GR[i]);
    return GR[i];
}

void reuniune(int i,int j)
{
    GR[grupa(i)] = grupa(j);
}
int main()
{
 fin>>N>>M;
    for(int i = 1;i <= M;++i)
    {
        fin>>x>>y>>c;
        VANS.push_back(make_pair(c,make_pair(x,y)));
    }

    for(int i = 1;i <= N; ++i)
        GR[i] = i;
    sort(VANS.begin(),VANS.end());
    for(int i = 0;i < M; ++i)
    {
        if (grupa(VANS[i].second.first) != grupa(VANS[i].second.second))
        {
            ANS=ANS+VANS[i].first;
            reuniune(VANS[i].second.first,VANS[i].second.second);
            VANSout.push_back(make_pair(VANS[i].second.first,VANS[i].second.second));
        }
    }
    fout<<ANS<<"\n";
    fout<<N-1<<"\n";
    for(int i = 0;i < N - 1; ++i)
        fout<<VANSout[i].first<<"  "<<VANSout[i].second<<"\n";
    return 0;
}