#include <bits/stdc++.h>
#define sc second
#define fs first

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int nmax=1e6+5;
vector < pair<int,pair<int,int> > > gr,sol;
int n,m,t[nmax],h[nmax],cost;

void init(int n)
{
    for (int i=1; i<=n; i++ )
    {
        h[i]=1;
        t[i]=i;
    }
}

int root(int nod)
{
    if ( t[nod]!=nod )
       t[nod]=root(t[nod]);
    return t[nod];
}

void unif(int x, int y)
{
    x=root(x);
    y=root(y);

    if ( x==y ) return;

    if ( h[x]<h[y] )
        t[x]=y;
    else
    {
        t[y]=x;
        if ( h[x]==h[y] )
            h[x]++;
    }
}

void krusky()
{
    cost=0;
    sort(gr.begin(),gr.end());
    init(n);

    for (auto i:gr ) // i.fs-costul, i.sc.fs-primul nod, i.sc.sc-al doilea nod
    {
        int x=root(i.sc.fs);
        int y=root(i.sc.sc);

        if ( x!=y )
        {
            unif(x,y);
            cost+=i.fs;
            sol.push_back(i);
        }
    }
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; i++ )
    {
        int x,y,c;
        f >> x >> y >> c;
        gr.push_back({c,{x,y}});
        gr.push_back({c,{y,x}});
    }

    krusky();

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

    for (auto i:sol )
       g << i.sc.fs << " " << i.sc.sc << '\n';
    return 0;
}