#include<fstream>
#include<vector>
#include<queue>
#define f first
#define s second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector< pair<int,int> >v[200001],solutie;
struct triplet{int x,y,c;};

struct comp
{
    bool operator()(triplet x,triplet y)
    {
        return x.c>y.c;
    }
};

priority_queue< triplet, vector<triplet>, comp> q;
int viz[200001],n,m,x,y,c,cost,tata;
void prim(int r)
{
    int i,vecin,nod_curent,cost_curent;
    triplet aux;
    viz[r]=1;
    for(i=0;i<v[r].size();i++)
    {
        aux.x=v[r][i].s;
        aux.y=r;
        aux.c=v[r][i].f;
        q.push(aux);
    }
    while(!q.empty())
    {
        nod_curent=q.top().x;
        cost_curent=q.top().c;
        tata=q.top().y;
        q.pop();
        if(viz[nod_curent]==0)
        {
            solutie.push_back({nod_curent,tata});
            viz[nod_curent]=1; cost+=cost_curent;
            for(i=0;i<v[nod_curent].size();i++)
            {
                aux.x=v[nod_curent][i].s;
                aux.y=tata;
                aux.c=v[nod_curent][i].f;
                q.push(aux);
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back(make_pair(c,y));
        v[y].push_back(make_pair(c,x));
    }
    prim(1);
    fout<<cost<<'\n';
    fout<<solutie.size()<<'\n';
    for(int i=0;i<solutie.size();i++) fout<<solutie[i].f<<" "<<solutie[i].s<<'\n';
    return 0;
}