#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

priority_queue < pair < int,int>> h;
const int N=400002,INF=N;
int n,d[N],pred[N],cost,m;
bool sel[N];
vector < pair < int,int> >a[N];

void read()
{
    int x,y,l;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>l;
        a[x].push_back(make_pair(y,l));
        a[y].push_back(make_pair(x,l));
    }
}

void prim()
{
     for(int i=2;i<=n;i++)
     {
         d[i]=INF;
     }
     h.push(make_pair(-d[1],1));
     int x,y,c;
     while(!h.empty())
     {
         while(!h.empty() && sel[h.top().second])
         {
             h.pop();
         }
         if(h.empty())
         {
            return;
         }
         x=h.top().second;
         cost+=d[x];
         sel[x]=true;
         h.pop();
         for(auto p:a[x])
         {
             y=p.first;
             c=p.second;
             if(c<d[y])
             {
                d[y] =c;
                pred[y]=x;
                h.push(make_pair(-d[y],y));
             }
         }
     }
}


int main()
{
    read();
    prim();
    out<<cost<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
    {
        out<<i<<' '<<pred[i]<<'\n';
    }
    return 0;
}