#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define MAXIM 200010
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct drum
{
    int N1,N2,DIST;
        bool operator<(const drum &altu)const
    {
        return DIST<altu.DIST;
    }
};
int n,m;
vector < drum > G[MAXIM];
queue < drum > q;
priority_queue < drum > pq;
int viz[MAXIM];
void APM()
{
    drum D;
    D.N1=1;
    D.DIST=0;
    pq.push(D);
    int SUM=0;
    while(!pq.empty())
    {
        drum toppq;
        toppq=pq.top();
        pq.pop();
        if(viz[toppq.N1]==0)
        {
                    viz[toppq.N1]=1;
        if(toppq.N1!=1)
        {
            SUM=SUM+(-toppq.DIST);
            drum nou;
            nou.N1=toppq.N1;
            nou.N2=toppq.N2;
            q.push(nou);

        }
        for(int i=0;i<G[toppq.N1].size();++i)
        {
            if(viz[G[toppq.N1][i].N1]==0)
            {
                drum nou2;
                nou2.N1=G[toppq.N1][i].N1;
                nou2.N2=toppq.N1;
                nou2.DIST=-G[toppq.N1][i].DIST;
                pq.push(nou2);
            }
        }
        }


    }
    g<<SUM<<endl<<n-1<<endl;
    while(!q.empty())
    {
        g<<q.front().N1<<" "<<q.front().N2<<endl;
        q.pop();
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b,c;
        f>>a>>b>>c;
        drum nou;
        nou.DIST=c;
        nou.N1=b;
        nou.N2=a;
        G[a].push_back(nou);
        nou.N1=a;
        nou.N2=b;
        G[b].push_back(nou);
    }
    APM();

    return 0;
}