#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#define maxn 200001
#define maxm 400001
#define inf 1001

using namespace std;

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

int h[maxn],d[maxn],e[maxn],where[maxn],c[maxn],used[maxn];
int n,m;

struct edge
{
    int x,y;
}apm[maxn];

vector <pair <int,int> > G[maxn];

void upheap (int x)
{
    int node = where[x];

    while (d[x] < d[h[node>>1]])
    {
        h[node]=h[node>>1];
        where[h[node]]=node;
        node>>=1;
    }
    h[node]=x;
    where[x]=node;
}

void downheap (int x)
{
    int node=where[x],ok=0;

    while (ok!=-1)
    {
      ok=-1;
      if (node<<1 <= n && d[x] > d[h[node<<1]]) ok=0;
      if ((node<<1)+1 <= n && d[x] > d[h[(node<<1)+1]])
      {
            if(ok==0) {if (d[h[(node<<1)+1]] < d[h[node<<1]]) ok=1;}
            else ok=1;
      }
      if (ok!=-1)
      {
          h[node]=h[(node<<1)+ok];
          where[h[node]]=node;
          node<<=1; node+=ok;
      }
    }
    h[node]=x;
    where[h[node]]=node;
}

void Prim()
{
    vector <pair<int,int> >::iterator it;
    int nr=0,s=0;

    for (int i=1; i<=n; ++i) {h[i]=i+1; where[i+1]=i;}
    for (int i=2; i<=n+1; i++) d[i]=inf;
    d[0]=-1001;

    for (it=G[1].begin(); it!=G[1].end(); ++it)
    {
        if (it->second < d[it->first])
        {
            d[it->first]=it->second;
            e[it->first]=1;
        }
        upheap (it->first);
    }

    used[1]=1;

    while (d[h[1]]!=inf)
    {
        apm[++nr].x=h[1];
        apm[nr].y=e[h[1]];
        s+=d[h[1]];
        used[h[1]]=1;

        int current=h[1];

        for (it=G[current].begin(); it!= G[current].end(); ++it)
        {
            if (used[it->first]) continue;
            if (it->second < d[it->first])
            {
                 d[it->first]=it->second;
                 e[it->first]=current;
            }
            upheap (it->first);
        }
        d[current]=inf;
        downheap (current);
    }

    fout<<s<<"\n"<<nr<<"\n";
    for (int i=1; i<=nr; i++)
        fout<<apm[i].x<<" "<<apm[i].y<<"\n";
}

int main()
{
    fin>>n>>m;
    int a,b,c;
    for (int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
        G[b].push_back(make_pair(a,c));
    }

    Prim ();
}