#include <iostream>
#include<vector>
#include <set>
#include<fstream>
using namespace std;
const int nmax=200000,mmax=400000,minf=-2000000000;
struct muchie
{
    int x,y,c;
    muchie(int x1=0,int y1=0,int c1=0)
    {
        x=x1;
        y=y1;
        c=c1;
    }
    bool operator < (const muchie & other) const
    {
        if(c!=other.c)
            return c<other.c;
        if(x!=other.x)
            return x<other.x;
        return y<other.y;
    }
};
muchie muchii[nmax+5];
vector<pair<int,int> > ve[nmax+5];
bool used[nmax+5];
int dist[nmax+5];
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int q,n,m,i,x,y,c,varf,dm,vecin,cost=0;
    muchie tm;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        ve[x].push_back(make_pair(c,y));
        ve[y].push_back(make_pair(c,x));
    }
    set<muchie> st;
    for(i=1;i<=n;i++)
    {
    used[i]=0;
    dist[i]=minf;
    }
    used[1]=1;
    dist[1]=0;
    for(i=0;i<ve[1].size();i++)
    {
        dm=ve[1][i].first;
        varf=ve[1][i].second;
        dist[varf]=dm;
        st.insert(muchie(1,varf,dm));
    }
    m=0;
    while(st.begin()!=st.end())
    {
        tm=(*st.begin());
        st.erase(st.find(tm));
        varf=tm.y;
        if(!used[varf])
        {

        used[varf]=1;
        cost=cost+tm.c;
        m++;
        muchii[m]=tm;
                   // cout<<"*"<<varf<<"\n";
        for(i=0;i<ve[varf].size();i++)
        {
            vecin=ve[varf][i].second;
            dm=ve[varf][i].first;


            if(!used[vecin])
            {
                     //       cout<<vecin<<"\n";
               if(dist[vecin]>dm || dist[vecin]==minf)
               {
                dist[vecin]=dm;
                st.insert(muchie(varf,vecin,dm));
               }
            }
        }
        }

    }
    fout<<cost<<"\n"<<m<<"\n";
    for(i=1;i<n;i++)
    {
        fout<<muchii[i].x<<" "<<muchii[i].y<<"\n";
    }
    return 0;
}