#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <bitset>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");
const int NMAX = 200001;
vector<pair<int,int> > muchii[NMAX];
vector<pair<int,int> > apm[NMAX];
set<pair<int,pair<int,int> > > heap;
bitset<NMAX> mark;
int n,m;
long long int apm_cost = 0;
int apm_edges = 0;

void citire()
{
    in>>n>>m;
    int x,y,z;
    for(int i = 1;i<=m;i++)
    {
        in>>x>>y>>z;
        muchii[x].push_back(make_pair(y,z));
        muchii[y].push_back(make_pair(x,z));
    }
    in.close();
}

void _apm()
{
    mark.set(1);
    int target,cost,source;
    for(unsigned int i = 0;i<muchii[1].size();i++)
    {
        target = muchii[1][i].first;
        cost = muchii[1][i].second;
        heap.insert(make_pair(cost,make_pair(1,target)));
    }
    while(!heap.empty())
    {
            source = heap.begin()->second.first;
            target = heap.begin()->second.second;
            cost = heap.begin()->first;
             heap.erase(heap.begin());
            if(!mark.test(target))
            {
                mark.set(target);
                apm[source].push_back(make_pair(target,cost));
                apm_cost += cost;
                apm_edges++;
                for(unsigned int i=0;i<muchii[target].size();i++)
                    if(!mark.test(muchii[target][i].first))
                    heap.insert(make_pair(muchii[target][i].second,make_pair(target,muchii[target][i].first)));
            }
    }
}

void print_apm()
{
    out<<apm_cost<<"\n";
    out<<apm_edges<<"\n";
   for(int i=1;i<=n;i++)
       for(unsigned int j=0;j<apm[i].size();j++)
        out<<i<<" "<<apm[i][j].first<<"\n";
    out.close();
}

int main()
{
    citire();
    _apm();
    print_apm();
    return 0;
}