#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int n,m,x,y,c,nr,cost_total,i,j,dist[200001],tata[200001],viz[200001];
const int INF=300000;
ifstream f("apm.in");
ofstream g("apm.out");
vector<pair<int,int>>cost[200001];
vector<pair<int, int>> rezultat;
int main()
{
      f>>n>>m;
    for(i=1;i<=m;++i)
    {
         f>>x>>y>>c;
        cost[x].push_back(make_pair(y,c));
        cost[y].push_back(make_pair(x,c));


    }
    for(i=1;i<=n;++i)
        dist[i]=INF,tata[i]=-1;
    int start=1;
    dist[start]=0;
    for(int k=1;k<=n;++k)
    {
        int nod=-1, minim=INF;
        for(i=1;i<=n;++i)
            if(!viz[i]&&dist[i]<minim)
            minim=dist[i],nod=i;
            if(nod==-1)
                break;
        viz[nod]=1;
        cost_total+=minim;

       for(auto [vecin,c]:cost[nod])
       if(!viz[vecin]&&c<dist[vecin])
       {
        tata[vecin]=nod;
       dist[vecin]=c;
       }


    }
   g<<cost_total<<endl;
   g<<n-1<<endl;
    for(i=1;i<=n;++i)
    if(tata[i]!=-1)
       g<<tata[i]<<' '<<i<<endl;
    return 0;
}