#include<iostream>
#include<vector>
#include<set>
#include<fstream>
#include<algorithm>
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;
        return y<other.y;
    }
    bool operator == (const muchie & other) const
    {
        return (y==other.y && c==other.c);
    }
};
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 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;
        sort(ve[i].begin(),ve[i].end());
    }
    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)
                    {
                        if(st.find(muchie(varf,vecin,dist[vecin]))!=st.end())
                        st.erase(st.find(muchie(varf,vecin,dist[vecin])));
                        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;
}