#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int DN=1e6+5;
int n,m,pr[DN],sol[DN],f,cnt,g,cost,viz[DN];
pair<int,pair<int,int> >mc[DN];
set<pair<int,int> >s;
long long sum;
vector<pair<int,int> >v[DN];

int main()
{
    FILE *fin=fopen("apm.in","r");
    FILE *fout=fopen("apm.out","w");

    fscanf(fin,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d%d",&mc[i].y.x,&mc[i].y.y,&mc[i].x);
        f=mc[i].y.x;
        g=mc[i].y.y;
        cost=mc[i].x;
        v[f].push_back({g,cost});
        v[g].push_back({f,cost});
    }
    for(int i=0;i<n+1;i++)
    {
        pr[i]=-1;
        sol[i]=2e9;
        s.insert({sol[i],i});
    }
    if(m==0)
    {
        fprintf(fout,"%d",0);
        return 0;
    }
    s.erase(s.find({sol[1],1}));
    sol[1]=0;
    viz[1]=1;
        for(auto i:v[1])
            if(!viz[i.x])
            {
                if(sol[i.x]<=i.y)
                    continue;
                s.erase(s.find({sol[i.x],i.x}));
                sol[i.x]=i.y;
                s.insert({sol[i.x],i.x});
                pr[i.x]=1;
            }
    ///aplic alg lui prim
    while(cnt<n-1)
    {
        //cout<<s.begin()->x<<' '<<s.begin()->y<<'\n';
        cnt++;
        sum+=s.begin()->x;
        int nod=s.begin()->y;
        s.erase(s.begin());
        viz[nod]=1;
        for(auto i:v[nod])
            if(!viz[i.x])
            {
                if(sol[i.x]<=i.y)
                    continue;
                s.erase(s.find({sol[i.x],i.x}));
                sol[i.x]=i.y;
                s.insert({sol[i.x],i.x});
                pr[i.x]=nod;
            }
    }

    ///afisez arborele
    fprintf(fout,"%lld\n",sum);
    fprintf(fout,"%d\n",cnt);
    for(int i=0;i<=n;i++)
    {
        if(pr[i]==-1)
            continue;
        fprintf(fout,"%d %d\n",i,pr[i]);
    }

}