#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;
priority_queue< pair< pair<int,int>, int >, vector< pair< pair<int,int>, int > >, greater< pair< pair<int,int>, int > > >q;
int viz[200001],n,m,x,y,c,cost,tata;
void prim(int r)
{
    int i,vecin,nod_curent,cost_curent;
    viz[r]=1;
    for(i=0;i<v[r].size();i++)
        q.push({{v[r][i].f,v[r][i].s},r});
    while(!q.empty())
    {
        nod_curent=q.top().f.s;
        cost_curent=q.top().f.f;
        tata=q.top().s;
        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++)
                q.push({{v[nod_curent][i].f,v[nod_curent][i].s},nod_curent});
        }
    }
}
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;
}