#include <fstream>
#include <vector>
#include <queue>
#define NMAX 200002
#define MMAX 400002
#define INF 1e9

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m;
int start=1;
int cost_apm;

struct varf{
    int x,c;
    friend bool operator < (varf a,varf b);
};
vector<varf> G[NMAX];

 bool operator < (varf a,varf b)
{
    return a.c>b.c;
}

void prim();
int cmin[NMAX];
int pre[NMAX];
int uz[NMAX];

priority_queue<varf> pq;

int main()
{
    int i,x,y,c;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        G[x].push_back({y,c});
        G[y].push_back({x,c});
    }
    prim();
    fout<<cost_apm<<'\n';
    fout<<n-1<<'\n';
    for(i=2; i<=n; i++)
        fout<<i<<' '<<pre[i]<<'\n';
    return 0;
}

void prim()
{
    int i;
    int varf,cost_varf,vecin,cost_vecin;
    //initializare
    for(i=1; i<=n; i++)
    {
        cmin[i]=INF;
        pre[i]=start;
    }
    cmin[start]=0;
    pre[start]=0;
    pq.push({start,0});
    while(!pq.empty())
        {
         varf=pq.top().x;
         cost_varf=pq.top().c;
         pq.pop();
         if(uz[varf]) continue;
         uz[varf]=1;
         cost_apm+=cost_varf;
         for(i=0; i<G[varf].size(); i++)
            {
             vecin=G[varf][i].x;
             cost_vecin=G[varf][i].c;
             if(!uz[vecin] && cmin[vecin]>cost_vecin)
                {
                    cmin[vecin]=cost_vecin;
                    pq.push({vecin,cmin[vecin]});
                    pre[vecin]=varf;
                }
            }
        }
}