#include"bits/stdc++.h"
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

#define cin fin
#define cout fout

const int NMAX=2e5+10;
struct mm{
    int nod1, nod2, cost;
    bool operator()(mm x, mm y) const
    {
        if(x.cost==y.cost)
        {
            if(x.nod1==y.nod1)
                return x.nod2<y.nod2;
            return x.nod1<y.nod1;
        }
        return x.cost<y.cost;
    }
}aux;

set<mm, mm>mord;
int viz[NMAX];
vector<mm>answ;
int n, nod1, nod2, cost, m, total;
vector<mm>muchii[NMAX];

void read()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>nod1>>nod2>>cost;
        muchii[nod1].push_back({nod1, nod2, cost});
        muchii[nod2].push_back({nod1, nod2, cost});
    }
}


void solve()
{
    viz[1]=1;
    for(auto el:muchii[1])
        mord.insert(el);
    while(!mord.empty())
    {
        aux=*mord.begin();
        if(viz[aux.nod1]==0)
            swap(aux.nod1, aux.nod2);
        if(viz[aux.nod1]*viz[aux.nod2]==0)
        {
            viz[aux.nod2]=1;
            for(auto el:muchii[aux.nod2])
                mord.insert(el);
            answ.push_back(aux);
            total+=aux.cost;
        }
        else
            mord.erase(mord.begin());
    }
    cout<<total<<"\n";
    cout<<answ.size()<<"\n";
    for(auto el: answ)
        cout<<el.nod1<<" "<<el.nod2<<"\n";
}

int main()
{
    read();
    solve();


    return 0;
}