# include <fstream>
# include <vector>
# define DIM 200001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,i,x,y,z,l,t,c,w[DIM],h[DIM],p[DIM],a[DIM];
vector<pair<int,int> > s,v[DIM];
void read()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
         {
          f>>x>>y>>z;
          v[x].push_back(make_pair(y,z));
          v[y].push_back(make_pair(x,z));
          w[x]=w[y]=200000001;
         }
}
void up_heap()
{
    t=c>>1;
    while(t>0&&w[h[t]]>w[h[c]])
          {
           swap(p[h[t]],p[h[c]]);
           swap(h[t],h[c]);
           c=t;
           t=c>>1;
          }
}
void down_heap()
{
    t=1;
    c=t<<1;
    c+=(c<l&&w[h[c]]>w[h[c+1]]);
    while(c<=l&&w[h[t]]>w[h[c]])
           {
            swap(p[h[t]],p[h[c]]);
            swap(h[t],h[c]);
            t=c;
            c=t<<1;
            c+=(c<l&&w[h[c]]>w[h[c+1]]);
           }
}
void Prim()
{
    int d;
    w[1]=z=0;
    h[++l]=1;
    p[1]=l;
    while(l>0)
           {
            x=h[1];
            if(a[x])
               {
                z+=w[x];
                s.push_back(make_pair(a[x],x));
               }
            p[h[l]]=1;
            h[1]=h[l--];
            down_heap();
            d=v[x].size();
            for(i=0;i<d;i++)
                if(w[v[x][i].first]>v[x][i].second)
                    {
                     w[v[x][i].first]=v[x][i].second;
                     a[v[x][i].first]=x;
                     if(!p[v[x][i].first])
                         {
                          h[++l]=v[x][i].first;
                          p[v[x][i].first]=l;
                         }
                     c=p[v[x][i].first];
                     up_heap();
                    }
           }
}
void write()
{
    n--;
    g<<z<<'\n'<<n<<'\n';
    for(i=0;i<n;i++)
          g<<s[i].first<<" "<<s[i].second<<'\n';
}
int main()
{
    read();
    Prim();
    write();
    f.close();
    g.close();
    return 0;
}