#include <fstream>
#include <algorithm>
using namespace std;

ifstream is("apm.in");
ofstream os("apm.out");

struct muchie{
    int x, y, z;
    bool operator < (const muchie& q) const
    {
        return z < q.z;
    }
};

int n, m, x, y, z;
int cost, a[200000], b[200000];
int t[200001];
muchie g[400001];

int main()
{
    is >> n >> m;
    for ( int i = 1; i <= m; ++i )
        is >> g[i].x >> g[i].y >> g[i].z;
    sort(g + 1, g + m + 1);
    //for ( int i = 1; i <= m; ++i )
      //  os << g[i].x << " " << g[i].y << " " << g[i].z << "\n";
    int cnt = n - 1;
    for ( int i = 1; i <= n; ++i )
        t[i] = i;
    for ( int i = 1; i <= m && cnt; ++i )
    {
        if ( t[g[i].x] != t[g[i].y] )
        {
            if ( g[i].x > g[i].y )
                t[g[i].x] = t[g[i].y];
            else
                t[g[i].y] = t[g[i].x];
            cost += g[i].z;
            a[cnt] = g[i].x;
            b[cnt] = g[i].y;
            --cnt;
        }
    }
    os << cost << "\n" << n - 1 << "\n";
    for ( int i = 1; i < n; ++i )
        os << a[i] << " " << b[i] << "\n";
    is.close();
    os.close();
    return 0;
}