#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct drum
{
    int nod,dist,nod2;
    bool operator<(const drum &altu)const
    {
        return dist<altu.dist;
    }
};

vector <drum> G[200010];
priority_queue <drum> pq;
queue <drum> q;
int viz[200010],s,n,m;

void apm()
{
    drum dr;
    dr.nod=1;
    dr.dist=0;
    pq.push(dr);
    while(!pq.empty())
    {
        dr = pq.top();
        pq.pop();
        if(!viz[dr.nod])
        {
            s+=-dr.dist;
            if(dr.nod!=1) q.push(dr);
            viz[dr.nod]=1;
            for(int i=0;i<G[dr.nod].size();i++)
                if(!viz[G[dr.nod][i].nod])
            {
                drum nou;
                nou.nod=G[dr.nod][i].nod;
                nou.dist=-G[dr.nod][i].dist;
                nou.nod2=dr.nod;
                pq.push(nou);
            }
        }
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        drum nou;
        nou.nod=b;
        nou.dist=c;
        G[a].push_back(nou);
        nou.nod=a;
        G[b].push_back(nou);
    }
    apm();
    g<<s<<'\n'<<n-1<<'\n';
    while(!q.empty())
    {
        drum sol;
        sol=q.front();
        q.pop();
        g<<sol.nod<<' '<<sol.nod2<<'\n';
    }
    f.close();
    g.close();
    return 0;
}