#include <fstream>
#include <vector>
#include <iostream>
#include <list>
#define INF (1<<30)-1
#define nmax 200001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector < int > h;
vector < pair <int, int> > v[nmax],sol;
int n,ph[nmax],t[nmax],d[nmax],len,viz[nmax];

void sift(int nod)
{
    int son=nod, f1,f2;
    do
    {
        nod=son; f1=2*nod; f2=2*nod+1;
        if(f1<h.size() && d[h[son]]>d[h[f1]]) son=f1;
        if(f2<h.size() && d[h[son]]>d[h[f2]]) son=f2;

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

    }while(nod!=son);

}

void percolate(int nod)
{
    while(d[h[nod/2]]>d[h[nod]] && nod/2>1)
    {
        ph[h[nod]]=nod/2;
        ph[h[nod/2]]=nod;
        swap(h[nod],h[nod/2]);
        nod=nod/2;
    }
}

int main()
{
    int i,j,m,x,y,c,nod;
     f>>n>>m;
    for(i=0;i<m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    h.push_back(0);
    h.push_back(1);
    d[1]=0;
    for(i=2;i<=n;i++) d[i]=INF;
    while(h.size()>1)
    {
        nod=h[1]; viz[nod]=1; len+=d[nod]; d[nod]=0;
        if(nod!=1) sol.push_back(make_pair(nod,t[nod]));
        for(i=0;i<v[nod].size();i++)
        {
            x=v[nod][i].first;
            y=v[nod][i].second;
            if(d[x]>y && !viz[x])
            {
                if(d[x]==INF)
                {
                   d[x]=y; t[x]=nod;
                   h.push_back(x);
                   ph[x]=h.size()-1;
                   percolate(ph[x]);
                }
                else
                {
                    d[x]=y; t[x]=nod;
                    percolate(ph[x]);
                }
            }
        }
        h[1]=h[h.size()-1];
        ph[h[1]]=1;
        h.pop_back();
        sift(1);
    }
    g<<len<<'\n'<<n-1<<'\n';
    for(i=0;i<sol.size();i++)
        g<<sol[i].first<<' '<<sol[i].second<<'\n';
}