#include<iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

vector<pair <int,pair<int,int> > > heap;
vector <pair<int,int> >A[200005];
vector <pair <int ,int> > M;
pair<int,pair<int,int> >  aux;
int n,m,x,y,c,*viz,cost,nod,v,contor=0,suma=0;

int main()
{
    f>>n>>m;
    viz=new int[n+1];
    for(int i=1;i<=n;i++)
        viz[i]=0;

    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        A[x].push_back(make_pair(y,c));
        A[y].push_back(make_pair(x,c));

    }

    for( int i=0;i<A[1].size();i++)
        {
            heap.push_back(make_pair(-A[1][i].second , make_pair(1,A[1][i].first)));
            push_heap(heap.begin(),heap.end());
        }

    viz[1]=1;

    while(contor<n-1)
    {
        pop_heap(heap.begin(),heap.end());
        aux=heap.back();
        heap.pop_back();
        cost=-aux.first;
        v=aux.second.first;
        nod=aux.second.second;

        if(viz[nod]==0)
        {
            M.push_back(make_pair(nod,v));
            suma=suma+cost;
            viz[nod]=1;
            contor++;
            for(int i=0;i<A[nod].size();i++)
            {
                heap.push_back(make_pair(-A[nod][i].second,make_pair(nod,A[nod][i].first)));
                push_heap(heap.begin(),heap.end());
            }

        }

    }

    g<<suma<<'\n'<<n-1<<'\n';
    for(int i=0;i<M.size();i++)
        g<<M[i].first<<" "<<M[i].second<<'\n';



    return 0;
}