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

using namespace std;

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

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

vector <muchie> G[200010];

int n,m,total;

void apm()
{
    int viz[200010]={0};
    priority_queue <muchie> pq;
    queue <muchie> q;
    muchie dr;
    dr.nod=1;
    dr.dist=0;
    pq.push(dr);
    while(!pq.empty())
    {
        dr=pq.top();
        pq.pop();
        if(!viz[dr.nod])
        {
            viz[dr.nod]=1;
            if(dr.nod!=1)
                {
                    muchie nou;
                    nou.nod=dr.nod;
                    nou.nod2=dr.nod2;
                    total+=(-dr.dist);
                    q.push(nou);
                }
            for(int i=0;i<G[dr.nod].size();i++)
                if(!viz[G[dr.nod][i].nod])
                {
                    muchie nou;
                    nou.nod=G[dr.nod][i].nod;
                    nou.nod2=dr.nod;
                    nou.dist=-G[dr.nod][i].dist;
                    pq.push(nou);
                }
        }
    }
    g<<total<<'\n'<<n-1<<'\n';
    while(!q.empty())
    {
        muchie m;
        m=q.front();
        g<<m.nod2<<' '<<m.nod<<'\n';
        q.pop();
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        muchie nou;
        nou.nod=b;
        nou.dist=c;
        G[a].push_back(nou);
        nou.nod=a;
        G[b].push_back(nou);
    }
    apm();
    f.close();
    g.close();

    return 0;
}