#include <iostream>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct drum{
    int a, b, c;
};

bool comp( drum x, drum xx )
{
    if( x.c == xx.c )
        return false;
    return x.c < xx.c;
}

const int maxN = 2e5;
int parinte[ maxN+1 ], dim[ maxN+1 ], n, m;
long long ans = 0;
vector<drum> adj;

void precal()
{
    for( int i = 1; i <= n; ++i )
    {
        dim[i] = 1;
        parinte[i] = i;
    }
}


int p( int x )
{
    if( parinte[x] != x )
    {
        int nextParinte = p( parinte[x] );
        parinte[x] = nextParinte;
        return nextParinte;
    }
    return x;
}

bool unf( int x, int y )
{
    int rootx = p(x), rooty = p(y);
    if( rootx == rooty )
        return false;
    else
    {
        if( dim[ rootx ] >= dim[ rooty ] )
        {
            parinte[ rooty ] = rootx;
            dim[ rootx ] += dim[ rooty ];
        }
        else
        {
            parinte[ rootx ] = rooty;
            dim[ rooty ] += dim[ rootx ];
        }
        return true;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);
    g.tie(nullptr);

    f >> n >> m;
    precal();
    for( int i = 1; i <= m; ++i )
    {
        int a, b, c;
        f >> a >> b >> c;
        drum r;
        r.a = a, r.b = b, r.c = c;
        adj.push_back( r );
    }
    sort( adj.begin(), adj.end(), comp );
    vector<pair<int, int> > ansList;
    for( int i = 0; i < adj.size(); ++i )
    {
        int u = adj[i].a, v = adj[i].b, w = adj[i].c;
        bool ok = unf( u,v );
        if( ok == true )
        {
            pair<int,int> rr;
            rr.first = u;
            rr.second = v;
            ans += w;
            ansList.push_back(rr);
        }
    }
    g << ans << "\n" << n-1 << "\n";
    for( int i = 0; i < ansList.size(); ++i )
    {
        g << ansList[i].first << " " << ansList[i].second << "\n";
    }
    return 0;
}