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

using namespace std;





int main()
{

    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m, x, y, z, s, nr, viz[200002];
    vector< vector < pair < int, int > > > liste;
    vector<pair<int,pair<int,int> > >heap;
    vector<pair<int,int> >muchii;
    pair<int,pair<int,int> >p;
    s = nr = 0;
    f >> n >> m;
    liste.resize( n + 1 );
    for( int i=1; i<=n; ++i )
        viz[i] = 0;
    for( int i=1; i<=m; i++ )
    {
        f >> x >> y >> z;
        liste[x].push_back(make_pair(y,z));
        liste[y].push_back(make_pair(x,z));
    }

    for( vector<pair<int,int> >::iterator it=liste[1].begin(); it!=liste[1].end(); ++it )
    {
        heap.push_back(make_pair(-it->second,make_pair(1,it->first)));
        push_heap(heap.begin(),heap.end());
    }

    viz[1] = 1;

    while( nr<n-1 )
    {
        pop_heap(heap.begin(),heap.end());
        p = heap.back();
        heap.pop_back();

        x = p.second.first;
        y = p.second.second;
        z = -p.first;

        if( viz[y] == 0 )
        {
            muchii.push_back(make_pair(x,y));
            s += z;
            viz[y] = 1;
            nr++;
            for(vector<pair<int,int> >::iterator it=liste[y].begin(); it!=liste[y].end(); ++it )
                if( viz[it->first] == 0 )
                {
                    heap.push_back(make_pair(-it->second,make_pair(y,it->first)));
                    push_heap(heap.begin(),heap.end());
                }
        }
    }

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