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

using namespace std;

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

struct muchie
{
    int nod1,nod2,cost;
    bool operator<(const muchie&altu) const
    {
        return altu.cost<cost;
    }
};

vector <muchie> G[200010];

void APM(int n)
{
    int viz[200010]={},s=0;
    priority_queue <muchie> pq;
    queue <muchie> sol;
    muchie drum;
    drum.nod1=1;
    drum.cost=0;
    pq.push(drum);
    while(!pq.empty())
    {
        drum=pq.top();
        pq.pop();
        if(!viz[drum.nod1])
        {
            if(drum.nod1!=1) sol.push(drum);
            viz[drum.nod1]=1;
            s+=drum.cost;
            for(int i=0;i<G[drum.nod1].size();i++)
            {
                muchie nou;
                nou.nod1=G[drum.nod1][i].nod1;
                nou.cost=G[drum.nod1][i].cost;
                nou.nod2=drum.nod1;
                if(!viz[nou.nod1]) pq.push(nou);
            }
        }
    }
    g<<s<<'\n'<<n-1<<'\n';
    while(!sol.empty())
    {
        muchie drum=sol.front();
        sol.pop();
        g<<drum.nod2<<' '<<drum.nod1<<'\n';
    }
}

int main()
{
    int n,m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        muchie nou;
        nou.nod1=b;
        nou.cost=c;
        G[a].push_back(nou);
        nou.nod1=a;
        G[b].push_back(nou);
    }
    APM(n);
    return 0;
}