#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define comtinue continue
#define mp make_pair
#define MAX 200010
#define cout fout
typedef vector<pair<int, int> > :: iterator iter;
vector<pair<int, int> > G[MAX];
priority_queue < pair < int, int> > Q;


int n, m, x, y, c, s, nod, viz[MAX], dr;
pair<int, int> aux, rez[MAX];
int main()
{
    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y >> c;
        G[x].push_back(mp(y, c));
        G[y].push_back(mp(x, c));
    }
    s = 0;
    Q.push(mp(0, 1));
    while(Q.size())
    {
        aux = Q.top();
        Q.pop();
        nod = aux.second;
        if(viz[nod])
            comtinue;
        viz[nod] = 1;
        s -= aux.first;
        for(iter it = G[nod].begin() ; it != G[nod].end() ; it++)
        {
            if(!viz[it->first])
            {
                Q.push(mp(-it->second, it->first));
            }
            else if(it->second == -aux.first)
            {

                rez[++dr] = mp(it->first, nod);
            }
        }
    }
    cout << s << "\n";
    cout << dr << "\n";
    for(int i = 1 ; i <= dr ; i++)
    {
        cout << rez[i].first << " " << rez[i].second << "\n";
    }

}