#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

//scuze

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
#define mult 2000000000
int n, m, x, y, z, s;
vector<pair<int,int> >l[200001];
vector<pair<int,int> >mu;
int dist[200001], t[200001];
int main()
{
    f >> n >> m;

    for( int i=1; i<=m; ++i )
    {
        f >> x >> y >> z;
        l[x].push_back(make_pair(y,z));
        l[y].push_back(make_pair(x,z));
    }

    for( int i=1; i<=n; ++i )
        dist[i] = mult;
    dist[1] = -1;
    for( vector<pair<int,int> >::iterator it=l[1].begin(); it!=l[1].end(); ++it )
    {
        dist[it->first] = it->second;
        t[it->first] = 1;
    }
    int minim, tt;
    for( int i=1; i<n; ++i )
    {
        minim = mult;
        for( int j=1; j<=n; ++j )
            if( dist[j] < minim && dist[j] != -1 )
            {
                minim = dist[j];
                tt = j;
            }
        mu.push_back(make_pair(t[tt],tt));
        s += minim;

        for( vector<pair<int,int> >::iterator it=l[tt].begin(); it!=l[tt].end(); ++it )
            if( dist[it->first] > it->second && dist[it->first] != -1 )
            {
                dist[it->first] = it->second;
                t[it->first] = tt;
            }
        dist[tt] = -1;
    }

    g << s << '\n' << n-1 << '\n';
    for( vector<pair<int,int> >::iterator it=mu.begin(); it!=mu.end(); ++it )
        g << it->first << " " << it->second << '\n';

    return 0;
}