#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define f first
#define s second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
priority_queue < pair<int,pair<int,int> >, vector <pair<int,pair<int,int> > >, greater<pair<int,pair<int,int> > > > q;
pair<int,pair<int,int> > p;
vector < pair<int,int> > v[200010],rez;
int N,M,nr,fv[200010],C;
int main()
{
    int i,j,x,y,c;
    fin>>N>>M;
    for(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));
    }
    nr=0;
    fv[1]=1;
    C=0;
    for(auto it:v[1])
    {
        q.push(make_pair(it.f,make_pair(1,it.s)));
    }
    while(nr!=N-1)
    {
        p=q.top();
        q.pop();
        if(fv[p.s.s]==0)
        {
            C+=p.f;
            nr++;
            rez.push_back(make_pair(p.s.f,p.s.s));
            fv[p.s.s]=1;
            for(auto it:v[p.s.s])
            {
                if(fv[it.s]==0)
                q.push(make_pair(it.f,make_pair(p.s.s,it.s)));
            }
        }
    }
    fout<<C<<'\n'<<nr<<'\n';
    for(auto it:rez)
    {
        fout<<it.f<<" "<<it.s<<'\n';
    }
}