#include <fstream>
#include <cstring>

#define INF 0x7fffffff

#define gSize 200001
#define dSize 200001
#define TSize 200001
#define useSize 200001

using namespace std;

ifstream in;
ofstream out;

struct graf
{
    int nod,cost;
    graf *link;
}*g[gSize];

int use[useSize];
int T[TSize];
int d[dSize];

int N,cnt=0;

inline void addedge(int x,int y,int c)
{
    graf *p=new graf;
    p->nod=y;
    p->cost=c;
    p->link=g[x];
    g[x]=p;
}

inline void Prim()
{
    memset(use,0,sizeof(use));
    memset(T,0,sizeof(T));
    d[1]=-INF;
    for(int i=2;i<=N;++i) d[i]=INF;

    for(int nod,min;1;)
    {
        min=INF;
        for(int i=1;i<=N;++i)
            if(min>d[i]&&!use[i])
            {
                min=d[i];
                nod=i;
            }

        if(min==INF) return;

        use[nod]=1;
        if(nod!=1) cnt+=d[nod];
        for(graf *p=g[nod];p;p=p->link)
            if(d[p->nod]>p->cost&&T[nod]!=p->nod)
            {
                T[p->nod]=nod;
                d[p->nod]=p->cost;
            }
    }
}

int main()
{
    int M,x,y,c;
    in.open("apm.in");

    in>>N>>M;
    for(;M--;)
    {
        in>>x>>y>>c;
        addedge(x,y,c);
        addedge(y,x,c);
    }

    in.close();

    Prim();

    out.open("apm.out");

    out<<cnt<<'\n'<<N-1<<'\n';
    for(int i=2;i<=N;++i)
        out<<T[i]<<' '<<i<<'\n';

    out.close();

    return 0;
}