#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;
typedef pair<int, int> pr;
const int N_MAX=200011;
const int oo=1<<29;

vector<pr> G[N_MAX];
vector<pr>::const_iterator it, iend;
int lHeap;
int d[N_MAX], H[N_MAX], P[N_MAX], apm[N_MAX];

inline void _swap(int& x, int& y) {int aux=x; x=y; y=aux;}
inline void DownHeap(int k)
{
    for(int son=k<<1; son <= lHeap; k=son, son<<=1)
    {
        if(son < lHeap && d[H[son]] > d[H[son+1]])
           ++son;
        if(d[H[k]] <= d[H[son]])
            return;
        _swap(H[k], H[son]);
        P[H[k]]=k;
        P[H[son]]=son;
    }
}
inline void UpHeap(int k)
{
    for(int key=d[H[k]], f=k>>1; k > 1 && key < d[H[f]]; k=f, f>>=1)
    {
         _swap(H[k], H[f]);
        P[H[k]]=k;
        P[H[f]]=f;
    }
}
inline int pop()
{
    int r=H[1];
    P[H[1]]=-1;
    H[1]=H[lHeap];
    P[H[1]]=1;
    --lHeap;
    DownHeap(1);
    return r;
}
inline void push(int x)
{
    H[++lHeap]=x;
    P[x]=lHeap;
    UpHeap(lHeap);
}
int main()
{
    int N, M, x, y, c, s=0, i;
    ifstream in("apm.in");
    ofstream out("apm.out");

    for(in>>N>>M; M; --M)
    {
        in>>x>>y>>c;
        G[x].push_back(pr(y, c));
        G[y].push_back(pr(x, c));
    }
    fill(d+1, d+N+1, oo);
    d[1]=0; push(1);
    for(i=0; i < N; ++i)
    {
        x=pop();
        s+=d[x];
        P[x]=-1;
        for(it=G[x].begin(), iend=G[x].end(); it < iend; ++it)
        {
            if(-1 == P[it->first])
                continue;
            if(d[it->first] > it->second)
            {
                apm[it->first]=x;
                if(oo == d[it->first])
                {
                    d[it->first]=it->second;
                    push(it->first);
                    continue;
                }
                d[it->first]=it->second;
                UpHeap(P[it->first]);
            }
        }
    }
    out<<s<<"\n"<<(N-1)<<"\n";
    s=0;
    for(i=2; i <= N; ++i)
      out<<i<<" "<<apm[i]<<"\n";
    return EXIT_SUCCESS;
}