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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX=2e5+5,INF=2e8+5;

int vec[NMAX],ans,v[NMAX],h[NMAX*2],pz[NMAX],l;

vector<vector<pair<int,int>>>adjl;
vector<pair<int,int>>vans;

void apm(int nod)
{
    for(int i=0;i<adjl[nod].size();i++)
    {
        int nod2=adjl[nod][i].first;
        int cost=adjl[nod][i].second;
        v[nod2]=min(v[nod2],cost);
        if(v[nod2]==cost)
        {
            vec[nod2]=nod;
        }
    }
}

void push(int poz)
{
    while((poz*2<=l&&v[h[poz]]>v[h[poz*2]])||(poz*2+1<=l&&v[h[poz]]>v[h[poz*2+1]]))
    {
        if(v[h[poz*2]]<v[h[poz*2+1]]||poz*2+1>l)
        {
            swap(h[poz],h[poz*2]);
            swap(pz[h[poz]],pz[h[poz*2]]);
            poz*=2;
        }
        else
        {
            swap(h[poz],h[poz*2+1]);
            swap(pz[h[poz]],pz[h[poz*2+1]]);
            poz=poz*2+1;
        }
    }
}


void pop(int poz)
{
    while(poz>1&&v[h[poz]]<v[h[poz/2]])
    {
        swap(h[poz],h[poz/2]);
        swap(pz[h[poz]],pz[h[poz/2]]);
        poz=poz/2;
    }
}

void heap(int nod)
{
    h[++l]=nod;
    pz[nod]=l;
    pop(l);
}

int heap2()
{
    int x=h[1];
    swap(h[1],h[l]);
    swap(pz[h[1]],pz[h[l]]);
    l--;
    push(1);
    pz[x]=0;
    return x;
}

int main()
{
    int n,m;
    fin>>n>>m;
    adjl.resize(n+1);
    for(int i=1;i<=m;i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        adjl[x].push_back({y,cost});
        adjl[y].push_back({x,cost});
    }
    for(int i=2;i<=n;i++)
    {
        v[i]=INF;
    }
    apm(1);
    for(int i=2;i<=n;i++)
    {
        heap(i);
    }
    for(int i=2;i<=n;i++)
    {
        int x=heap2();
        apm(x);
        ans+=v[x];
        vans.push_back({x,vec[x]});
        for(int j=0;j<adjl[x].size();j++)
        {
            int nod=adjl[x][j].first;
            if(pz[nod])
            {
                pop(pz[nod]);
            }
        }
    }
    fout<<ans<<endl;
    fout<<n-1<<endl;
    for(int i=0;i<n-1;i++)
    {
        fout<<vans[i].first<<" "<<vans[i].second<<endl;
    }
    return 0;
}