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

using namespace std;

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;

void citire()
{
    scanf("%d %d",&n,&m);
    int x,y,z;
    for(int i = 1;i<=m;i++)
    {
       scanf("%d %d %d",&x,&y,&z);
        muchii[x].push_back(make_pair(y,z));
        muchii[y].push_back(make_pair(x,z));
    }
   fclose(stdin);
}

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));
                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()
{
     for(int i=1;i<=n;i++)
       for(unsigned int j=0;j<apm[i].size();j++)
        apm_cost+=apm[i][j].second;
  cout<<apm_cost<<"\n";
  cout<<n-1<<"\n";
   for(int i=1;i<=n;i++)
       for(unsigned int j=0;j<apm[i].size();j++)
        printf("%d %d\n",i,apm[i][j].first);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    _apm();
    print_apm();
    fclose(stdout);
    return 0;
}