#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");

int n,m,op,t[200001],cost;
struct muchie{int x,y,c;} a[400001];
vector <pair<int,int>> sol;

int cmp (muchie a, muchie b)
{ return a.c < b.c; }

int radacina (int x)
{
if(t[x]==0) return x;
radacina(t[x]);
}

int main()
{
    fi>>n>>m;
    for(int i = 1 ; i<=m ; i++)
        fi>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+m+1,cmp);

    for(int i = 1 ; i<=m ; i++)
    {
        int r1=radacina(a[i].x);
        int r2=radacina(a[i].y);
        if (r1 != r2)
        {
            t[r1]=r2;
            sol.push_back({a[i].x,a[i].y});
            cost+=a[i].c;
        }
    }

    fo<<cost<<'\n';
    fo<<sol.size()<<'\n';
    for(auto p : sol)
        fo<<p.first<<" "<<p.second<<'\n';

    return 0;
}