#include <fstream>
#include <vector>
#define NMAX 200001

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

vector < pair <int, int> > G[NMAX],sol;
vector < int > h;

int dist[NMAX],ph[NMAX],t[NMAX];
int N,best=0;
bool in[NMAX];

void sift(int nod)
{
    int f1,f2,son=nod;

    do
    {
        nod=son;
        f1=2*nod; f2=2*nod+1;

        if(f1<h.size() && dist[h[f1]]<dist[h[son]]) son=f1;
        if(f2<h.size() && dist[h[f2]]<dist[h[son]]) son=f2;

        swap(h[son],h[nod]);
        ph[h[son]]=son;
        ph[h[nod]]=nod;

    }while(nod!=son);
}

void percolate(int nod)
{
    while(nod/2 && dist[h[nod]]<dist[h[nod/2]])
    {
        swap(h[nod],h[nod/2]);
        ph[h[nod]]=nod;
        ph[h[nod/2]]=nod/2;
        nod/=2;
    }
}
void adaugare(int val)
{
    h.push_back(val);
    ph[val]=h.size()-1;
    percolate(ph[val]);
}
int main()
{
    int M,i,x,y,d;

    f>>N>>M;
    while(M--)
    {
        f>>x>>y>>d;
        G[x].push_back(make_pair(y,d));
        G[y].push_back(make_pair(x,d));
    }

    h.push_back(1);
    dist[1]=0;
    t[1]=1;

    int nod;
    while(!h.empty())
    {
        nod=h.front();
        in[nod]=1;

        if(nod!=1)
        {
            sol.push_back(make_pair(nod,t[nod]));
            best+=dist[nod];
        }

        for(i=0;i<G[nod].size();i++)
        {
            y=G[nod][i].first;
            d=G[nod][i].second;

            if(!t[y])
            {
                dist[y]=d;
                t[y]=nod;
                adaugare(y);
            }
            else if(dist[y]>d && !in[y])
                {
                    dist[y]=d;
                    t[y]=nod;
                    percolate(ph[y]);
                }
        }

        h[0]=h[h.size()-1];
        ph[h[0]]=0;
        h.pop_back();
        sift(0);

    }

    g<<best<<'\n';
    g<<N-1<<'\n';
    for(i=0;i<sol.size();i++)
        g<<sol[i].first<<' '<<sol[i].second<<'\n';
}