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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m, x, y, z, s, nr, viz[200002];
vector<pair<int,int> >liste[200002];
vector<pair<int,pair<int,int> > >heap;
vector<pair<int,int> >muchii;
pair<int,pair<int,int> >p;

int main()
{
    f >> n >> m;

    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;
}