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

using namespace std;

#define MAX 200000

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

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;
        anod=PQ.top().second.first;
        nod=PQ.top().second.second;
        int x=PQ.top().first;
        PQ.pop();
        if(viz[nod])
            continue;
        nr-=x;
        viz[nod]=1;
        if(nod!=anod)
        {
            H[anod].push_back(nod);
            //H[nod].push_back(anod);
            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<<"\n";
    for(int i=1;i<=nrn;i++)
        for(int j=0;j<H[i].size();j++)
            fout<<i<<" "<<H[i][j]<<"\n";
    return 0;
}