#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <bitset>
#define DIM 100000

using namespace std;

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

char buff[DIM];
int poz = 0;
void Read(int &a)
{
    bool mns = false;
    while(!isdigit(buff[poz]))
    {
        if(buff[poz]=='-')
            mns = true;
        if(++poz == DIM)
        in.read(buff,DIM),poz = 0;
    }
    a = 0;
    while(isdigit(buff[poz]))
    {
        a = a*10 + buff[poz]-'0';
        if(++poz == DIM)
            in.read(buff,DIM),poz = 0;
    }
    if(mns)
        a = -a;
}


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

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

void print_apm()
{
    out<<apm_cost<<"\n";
    out<<n-1<<"\n";
    for(int i=2;i<=n;i++)
      out<<i<<" "<<pred[i]<<"\n";
}

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