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

using namespace std;

#define MAX 200005

ifstream fin("apm.in");
ofstream fout("apm.out");

const unsigned maxb = 8192;
unsigned ptr = maxb - 1;
char buf[maxb];

int getInt()
{
    int rez = 0, sgn = 1;
    while(!((buf[ptr] >= '0' && buf[ptr] <= '9') || buf[ptr] == '-'))
    {
        if(++ptr >= maxb)
        {
            fin.read(buf, maxb);
            ptr = 0;
        }
    }
    if(buf[ptr] == '-')
    {
        sgn = -1;
        if(++ptr >= maxb)
        {
            fin.read(buf, maxb);
            ptr = 0;
        }
    }
    while(((buf[ptr] >= '0' && buf[ptr] <= '9') || buf[ptr] == '-'))
    {
        rez = rez * 10 + buf[ptr] - '0';
        if(++ptr >= maxb)
        {
            fin.read(buf, maxb);
            ptr = 0;
        }
    }
    return sgn * rez;
}

vector < pair < int , int > > G[MAX];
vector < int > H[MAX];
priority_queue < pair < int , pair < int , int > > > PQ;
int viz[MAX];

int main()
{
    int n,m,nr=0,nrn=1;
    fin>>n>>m;
    while(m--)
    {
        int x,y,c;
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
        G[y].push_back(make_pair(x,c));
    }
    PQ.push(make_pair(0, make_pair(1,1)));

    while(!PQ.empty())
    {
        int nod,anod;
        pair<int, pair<int, int> > l;
        l=PQ.top();
        anod=l.second.first;
        nod=l.second.second;
        int x=l.first;
        PQ.pop();
        if(viz[nod])
            continue;
        nr-=x;
        viz[nod]=1;
        if(nod!=anod)
        {
            H[anod].push_back(nod);
            nrn++;
        }
        for(int i=0;i<int(G[nod].size());i++)
            if(!viz[G[nod][i].first])
                PQ.push(make_pair(-G[nod][i].second, make_pair(nod, G[nod][i].first)));
    }
    fout<<nr<<"\n"<<nrn-1<<"\n";
    for(int i=1;i<=n;i++)
        for(int j=0;j<H[i].size();j++)
            fout<<i<<" "<<H[i][j]<<"\n";
    return 0;
}