#include<fstream>
#include<vector>
#include<queue>
#define NM 200001
#define INF 2000000001
#include<stdio.h>

using namespace std;
ifstream f("apm.in");
//FILE *f=fopen("dijkstra.in","r");
ofstream g("apm.out");
//FILE *g=fopen("dijkstra.out","w");

int n, m, d[NM],inq[NM],t[NM],sel[NM],w;
long long ct;
struct  pereche{
    int y,c;
};

struct compar{
 bool operator()(int x,int y)
{
    return d[x]>d[y];
}
};

vector<pereche> G[NM],A;

priority_queue <int, vector<int>, compar> q;

void Citeste()
{
    int i, x,y;
    pereche u;
    f>>n>>m;
    //fscanf(f,"%d %d",&n,&m);
    for (i=1; i<=m; i++)
    {
        f>>x>>y>>u.c;

        //fscanf(f,"%d %d %d",&x,&u.y,&u.c);
        u.y=y;
        G[x].push_back(u);

        u.y=x;
        G[y].push_back(u);

    }

}
void Prim()
{
    int z,lg,i,nr;

    for (i=2; i<=n; i++) d[i]=INF;
    d[1]=0;
    ///inq[1]=1;
    q.push(1);
    nr=0;
    while (nr<n)
    {

        int j,im,y,c;
        pereche u;
        im=q.top(); q.pop();

        ///inq[im]=0;
        if(sel[im]==0)
            {
                nr++;
            sel[im]=1;
            ct=ct+d[im];
            u.y=im;
            u.c=t[im];
            A.push_back(u);

            for(j=0;j<G[im].size();j++)
            {
                y=G[im][j].y;
                c=G[im][j].c;

                if(sel[y]==0 && c<d[y])
                {
                    t[y]=im;
                    d[y]=c;

                    ///if(inq[y]==0)
                    {
                       /// inq[y]=1;
                        q.push(y);
                    }

                }
            }

    }
    }

}
void Scrie()
{
    int i;
    g<<ct<<'\n';
    g<<A.size()-1<<'\n';
    for (i=1; i<A.size(); i++)
        g<<A[i].y<<' '<<A[i].c<<'\n';
}
int main()
{
    Citeste();
    Prim();
    Scrie();
   return 0;
}