#include <fstream>
#include <queue>
#include <iterator>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

int nr,N,M;
long long sum;
bool viz[200100];

struct chestie{
int from, to, cost;
};

struct compare{
   bool operator()(const chestie& l, const chestie& r){
       return (l.cost > r.cost);
   }
 };

queue <int> qnode;
priority_queue <chestie , vector<chestie>, compare> pq;

vector <pair<int,int> > List[200200],sol;
vector <pair<int,int> > :: iterator it;

inline void scan();
inline void print();
inline void primsalgorithm();

int main()
{
    scan();
    primsalgorithm();
    print();
    return 0;
}

inline void primsalgorithm()
{
    int cn=0, nn=0;
    ///cn=current node;
    ///nn=next node;
    nr=0;
    qnode.push(1);
    viz[1]=1;

    while(!qnode.empty() && nr<N)
    {
        cn=qnode.front();
        qnode.pop();

        for( it=List[cn].begin(); it!=List[cn].end(); ++it )
            if(!viz[(*it).second])
                pq.push({cn,(*it).second, (*it).first});

        nn=pq.top().to;
        while(!pq.empty() && viz[nn]==1)
        {
            pq.pop();
            nn=pq.top().to;
        }

        if(!viz[nn])
        {
            qnode.push(nn);
            sum+=pq.top().cost;
            sol.push_back({pq.top().from,pq.top().to});
            ++nr;
            viz[nn]=1;
            pq.pop();
        }
    }
}

inline void scan()
{
    int fromnode,tonode,cost;
    cin>>N>>M;
    for(int i=1; i<=M; ++i)
    {
        cin>>fromnode>>tonode>>cost;
        List[fromnode].push_back({cost,tonode});
        List[tonode].push_back({cost,fromnode});
    }
}

inline void print()
{
    cout<<sum<<'\n'<<nr<<'\n';
    for(int i=0; i<nr; ++i, cout<<'\n')
        cout<<sol[i].first<<' '<<sol[i].second;
}