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

using namespace std;

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

struct muchie
{
    int nod, dist, nod2;
    bool operator < (const muchie &altu)const
    {
        return dist > altu.dist;
    }
};

vector <muchie> G[200010];
priority_queue <muchie> pq;
queue <muchie> sol;
int n,m,viz[200010],s;

void APM()
{
    muchie nou;
    nou.nod=1;
    nou.dist=0;
    pq.push(nou);
    while(!pq.empty())
    {
        nou=pq.top();
        pq.pop();
        if(!viz[nou.nod])
        {
            viz[nou.nod]=1;
            s+=nou.dist;
            if(nou.nod!=1) sol.push(nou);
            for(int i=0;i<G[nou.nod].size();i++)
                if(!viz[G[nou.nod][i].nod])
            {
                muchie nou2;
                nou2.nod=G[nou.nod][i].nod;
                nou2.dist=G[nou.nod][i].dist;
                nou2.nod2=nou.nod;
                pq.push(nou2);
            }
        }
    }
    g<<s<<'\n'<<n-1<<'\n';
    while(!sol.empty())
    {
        muchie nou;
        nou=sol.front();
        sol.pop();
        g<<nou.nod<<' '<<nou.nod2<<'\n';
    }
}

int main()
{
    f>>n>>m;
    while(m--)
    {
        int a,b,c;
        f>>a>>b>>c;
        muchie nou;
        nou.nod=b;
        nou.nod2=a;
        nou.dist=c;
        G[a].push_back(nou);
        nou.nod=a;
        nou.nod2=b;
        G[b].push_back(nou);
    }
    APM();
    return 0;
}