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

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

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()
{
    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()
{
    cout<<apm_cost<<"\n";
    cout<<n-1<<"\n";
    for(int i=2;i<=n;i++)
      printf("%d %d\n",i,pred[i]);
}

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