#include <bits/stdc++.h>
#define DimMax 200000

using namespace std;

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

int n, m;
int x, y, c;
long long smin;
vector<pair<int, int> > adj[DimMax + 1];///{nod, cost}
priority_queue<pair<pair<int, int>, int> > pq;///{cost, nod, sursa}
vector<pair<int, int> > ans;
bool viz[DimMax + 1];

int main()
{
    fin >> n >> m;
    for ( int i = 1; i <= m; i++ )
    {
        fin >> x >> y >> c;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }
    viz[1] = 1;
    for ( auto v: adj[1] )
        pq.push({{-v.second, v.first}, 1});

    //fout << 1 << " ";
    while ( !pq.empty() )
    {
        pair<pair<int, int>, int> x = pq.top(); pq.pop();
        if ( viz[x.first.second] ) continue;
        viz[x.first.second] = 1;
        smin -= x.first.first;
        ans.push_back({x.first.second, x.second});
        for ( auto v: adj[x.first.second] )
            if ( !viz[v.first] )
                pq.push({{-v.second, v.first}, x.first.second});
    }

    fout << smin << '\n';
    fout << n - 1 << '\n';
    for ( pair<int, int> x: ans )
        fout << x.first << " " << x.second << '\n';
    return 0;
}