#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

int n,m,cost,viz[200005],sol1[200005],sol2[2000050],nrsol;

vector<pair<int,int> >g[200005];

struct muchie
{
    int x,y,c;
    bool operator<(muchie b) const
    {
        return c>b.c;
    }
};



priority_queue<muchie,vector<muchie>>q;

void citire()
{
    ifstream fin("apm.in");
    fin>>n>>m;
    int x,y,c;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
        g[y].push_back(make_pair(x,c));
    }
}

void rez()
{
    viz[1]=1;
    int cat;
    cat=g[1].size();
    for(int i=0;i<cat;i++)
        if(viz[g[1][i].first]==0)
        {
            muchie nou;
            nou.x=1;
            nou.y=g[1][i].first;
            nou.c=g[1][i].second;
            q.push(nou);
        }
    for(int k=0;k<n;k++)
    {
        while(!q.empty()&&viz[q.top().y])
            q.pop();
        if(!q.empty())
        {
            cost+=q.top().c;
            int nr1,nr2;
            nr2=q.top().y;
            nr1=q.top().x;
            q.pop();
            viz[nr2]=1;
            sol1[nrsol]=nr1;
            sol2[nrsol]=nr2;
            nrsol++;
            cat=g[nr2].size();
            for(int i=0;i<cat;i++)
                if(viz[g[nr2][i].first]==0)
                {
                    muchie nou;
                    nou.x=nr2;
                    nou.y=g[nr2][i].first;
                    nou.c=g[nr2][i].second;
                    q.push(nou);
                }
        }
    }
}

void afisare()
{
    ofstream fout("apm.out");
    fout<<cost<<"\n"<<n-1<<"\n";
    for(int i=0;i<nrsol;i++)
        fout<<sol1[i]<<" "<<sol2[i]<<"\n";
}

int main()
{
    citire();
    rez();
    afisare();
    return 0;
}