#include <fstream>
#include <vector>
using namespace std;
#define NMAX 200005
#define NMAX2 400005
#define pb push_back
#define S <<" "<<
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,rez;
int heap_val[NMAX2],heap_nod[NMAX2],heap_nod_aux[NMAX2],length,drum[NMAX],way[NMAX],nr[NMAX];
vector <int> v[NMAX],cost[NMAX];
bool viz[NMAX];
void scoate_poz1();
void solve();
void sch(int &a,int &b);
void baga(int val,int nod);
void read()
{
    fin>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v[a].pb(b);
        v[b].pb(a);
        cost[a].pb(c);
        cost[b].pb(c);
    }
}
void graf_tipar()
{
    for(int i=1;i<=n;i++)
        for(int j=0;j<v[i].size();j++)
            fout<<i S v[i][j] S cost[i][j]<<"\n";
}
void heap_tipar()
{
    fout<<"---------- BEGIN Heap_tipar :\n";
    for(int i=1;i<=length;i++)
        fout<<heap_val[i]<<" ";
    fout<<"\n";
    for(int i=1;i<=length;i++)
        fout<<heap_nod[i]<<" ";
    fout<<"\n";
    for(int i=1;i<=length;i++)
        fout<<heap_nod_aux[i]<<" ";
    fout<<"\n-------- END Heap_tipar  \n";
}
void nr_tipar()
{
    fout<<"NR : ";
    for(int i=1;i<=n;i++)
        fout<<nr[i]<<" ";
    fout<<"\n";
}
void drum_tipar()
{
    fout<<"DRUM : ";
    for(int i=1;i<=n;i++)
        fout<<drum[i]<<" ";
    fout<<"\n";
}
int main()
{
    read();
    solve();
  //  heap_tipar();
  //  fout<<rez;
  //  graf_tipar();
   // drum_tipar();
    fout<<rez<<"\n"<<n-1<<"\n";
    for(int i=2;i<=n;i++)
        fout<<way[i]<<" "<<i<<"\n";
}
void baga(int val,int nod,int nod_aux)
{
    length ++ ;
   // nr[nod]++;
    heap_val[length] = val;
    heap_nod[length] = nod;
    drum[nod]=val;
    heap_nod_aux[length] = nod_aux;
    int c = length / 2,poz=length;
    while(heap_val[c] > heap_val[poz] && c)
    {
        sch(heap_val[c],heap_val[poz]);
        sch(heap_nod[c],heap_nod[poz]);
        sch(heap_nod_aux[c],heap_nod_aux[poz]);
        poz = c;
        c /= 2;
    }
}
void scoate_poz1(int val)
{
    int poz=val,c=val*2;
    heap_val[1]=heap_val[length];
    heap_nod[1]=heap_nod[length];
    heap_nod_aux[1]=heap_nod_aux[length];
    length -- ;
    while(c <= length)
    {
        if(c < length && heap_val[c] > heap_val[c+1]) c++;
        if(heap_val[poz] <= heap_val[c]) return;
        sch(heap_val[c],heap_val[poz]);
        sch(heap_nod[c],heap_nod[poz]);
        sch(heap_nod_aux[c],heap_nod_aux[poz]);
        poz = c;
        c *= 2;
    }
}
void sch(int &a,int &b)
{
    int c=a;
    a=b;
    b=c;
}
void solve()
{
    viz[1] = true;
    int i,stop=n-1,nod;
    for(i=0;i<v[1].size();i++)
        baga(cost[1][i],v[1][i],1);
    while(stop)
    {
        if(viz[heap_nod[1]] == false)
        {
            nod=heap_nod[1];
            rez += heap_val[1];
            way[nod] = heap_nod_aux[1];
            scoate_poz1(1);
            for(i=0;i<v[nod].size();i++)
            {
                if(viz[v[nod][i]] == false)
                {
                    baga(cost[nod][i] , v[nod][i] , nod);
                }
            }
            stop--;
            viz[nod] = true;
           // nr_tipar();
        }
        else
            scoate_poz1(1);
       //   nr_tipar();
       // heap_tipar();
    }
}