#include <iostream>

#include <fstream>

#include <vector>

#include <algorithm>

#define Nmax 200005



using namespace std;



ifstream f("apm.in");

ofstream g("apm.out");



struct apm{

int x, y, c;

}v[400005];



long long sm;

int n, m, x, y, c;

int tt[Nmax];

vector <pair <int, int> > sol;



bool cmp(apm a, apm b)

{

    return a.c < b.c;

}



int root(int x)

{

    int r=x;

    while(r!=tt[r]) r=tt[r];



    while(x!=tt[x])

    {

        int y=tt[x];

        tt[x]=r;

        x=y;

    }

    return r;

}



int main()

{

    f >> n >> m;

    for (int i = 1; i <= m; i++)

    {

        f >> x >> y >> c;

        v[i]={x, y, c};

    }

    sort(v+1, v+m+1, cmp);

    for (int i = 1; i <= n; i++) tt[i]=i;



    for (int i = 1; i <= m; i++)

    {

        int x=v[i].x, y=v[i].y;

        int X=root(x), Y=root(y);

        if(X!=Y)

        {

            sm+=v[i].c;

            tt[X]=Y;

            sol.push_back({x, y});

        }

    }

    g << sm << '\n' << sol.size() << '\n';

    for (auto i:sol)

        g << i.first << " " << i.second << '\n';



    return 0;

}