#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100002
#define INF 1e9

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

int n,m;
struct varf{int x,c;};
vector<varf> G[NMAX];

void prim();
int start=1;
int cmin[NMAX];
int pre[NMAX];
int uz[NMAX];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; //first este costul minim, second este vfmin
int cost_apm;

int main()
{
    int i,a,b,cost,suma=0;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        {
         fin>>a>>b>>cost;
         G[a].push_back({b,cost});
         G[b].push_back({a,cost});
        }
    prim();
    fout<<cost_apm<<'\n';
    fout<<n-1<<'\n';
    for(i=1; i<=n; i++)
        if(pre[i])
            fout<<pre[i]<<' '<<i<<'\n';
    return 0;
}

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