#include <bits/stdc++.h>
#define N 200008

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
struct muchie
{
    int c, y;
};
vector< pair<int, int> > g[N], h[N];
set< pair<int, int> > q;
int v[N];
bool viz[N];

void Citire()
{
    int i;
    int x, y, c;
    fin >> n >> m;
    for( i=1; i<=m; i++ )
    {
        fin >> x >> y >> c;
        g[x].push_back( {c, y} );
        g[y].push_back( {c, x} );
    }
}

int sol[N];

void Rezolvare()
{
    for( int i=1; i<=n; i++ )
        v[i] = 1e9;

    int s = 0;
    v[1] = 0;
    q.insert( {0, 1} );
    while( !q.empty() )
    {
        int nod = q.begin()->second;
        s += q.begin()->first;
        q.erase(q.begin());
        viz[nod] = 1;

        for( auto e : g[nod] )
        {
            if( !viz[e.second] && e.first < v[e.second] )
            {
                if( v[e.second] != 1e9 )
                    q.erase(q.find({v[e.second], e.second}));
                q.insert(e);
                v[e.second] = e.first;
                sol[e.second] = nod;
            }
        }
    }
    fout << s << "\n";
    fout << n - 1 << "\n";
    for( int i=1; i<=n; i++ )
        if( sol[i] != 0 )
            fout << sol[i] << " " << i << "\n";
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}