#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
int n,m,viz[400001],nr=0;
long cost_total;
vector <pair<int,int> > v[400001];
vector <int> solutie[400001];
ifstream f("apm.in");
ofstream g("apm.out");

void parcurgere(int nod)
{
    viz[nod]=1;
    for(int i=0; i<v[nod].size();i++)
        if(viz[v[nod][i].first]==0)
        {
           // parcurgere(v[nod][i].first);
            solutie[nod].push_back(v[nod][i].first);
            cost_total+=v[nod][i].second;
            viz[v[nod][i].first]=1;
            nr++;
        }

}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    int ok=0;
    for(int nod=1;nod<=n;nod++)
    while(ok==0)
    {
        ok=1;
        for(int i=0;i<v[nod].size();i++)
        if(v[nod][i].second>v[nod][i+1].second)
        {
            swap (v[nod][i].first,v[nod][i+1].first);
            swap (v[nod][i].second,v[nod][i+1].second);
            ok=0;
        }
    }
    for(int i=1;i<=n;i++)
            parcurgere(i);

    g<<cost_total<<"\n";
    g<<nr<<"\n";
    for(int i=1;i<=n;i++)
        for(int j=0;j<solutie[i].size();j++)
        g<<i<<" "<<solutie[i][j]<<"\n";

    return 0;
}