#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
const int NMAX=200001,
          INF=1<<20;

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

struct muchie
{
    int y,w;
    muchie(int yy=0,int ww=0):y(yy),w(ww) {}
    bool operator<(const muchie &m) const
    {
        return w>m.w;
    }
};

int n,m,cost;
int t[NMAX],d[NMAX];

priority_queue<muchie>q;
vector<muchie>g[NMAX];
bool viz[NMAX];

void citire()
{
    fin>>n>>m;
    int x,y,cost;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>cost;
        g[x].push_back(muchie(y,cost));
        g[y].push_back(muchie(x,cost));
    }
}

void Prim()
{
    for(int i=2;i<=n;i++)
        d[i]=INF;
     q.push(muchie(1,0));
     while(!q.empty())
     {
         int x=q.top().y;
         q.pop();
         if(viz[x]) continue;
         viz[x]=1;
         cost+=d[x];
         for(auto &m:g[x])
            if(m.w<d[m.y]&&!viz[m.y])
         {
             t[m.y]=x;
             d[m.y]=m.w;
             q.push(m);
         }
     }
}

void afisare()
{
    fout<<cost<<'\n'<<n-1<<'\n';
    for(int i=1; i<=n; i++)
        if(t[i]!=0)
        fout<<i<<' '<<t[i]<<'\n';
}

int main()
{
    citire();
    Prim();
    afisare();
    fin.close();
    fout.close();
    return 0;
}