#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define N 200005
#define oo 2000000000
using namespace std;
int n,m;
struct str
{
    int nr,c;
};
vector <str> sol;
vector <int> nod;
int suma;
vector <str> a[N];
int v[N],poz[N];
bool Comp(str x, str y)
{
    return x.c<y.c;
}
void Read()
{
    ifstream fin("apm.in");
    fin>>n>>m;
    int x,y,cost,i;
    str w;
    for( i=1; i<=m; i++)
    {
        fin>>x>>y>>cost;
        w.nr=y;
        w.c=cost;
        a[x].push_back(w);
        w.nr=x;
        a[y].push_back(w);
    }
    int lg;
    for(i=1; i<=n; i++)
    {
        lg=a[i].size();
        sort(a[i].begin(),a[i].begin()+lg,Comp);
    }
}
void  Salv()
{
    int nrv=n-1;
    int i,minmuc,j,x,newnod,oldnod;
    str w;
    nod.push_back(1);
    v[1]=1;
    while(nrv)
    {
        nrv--;
        minmuc=oo;
        for(i=0; i<nod.size(); i++)
        {

            x=nod[i];
            j=poz[x];
            while(v[a[x][j].nr] && j+1<a[x].size())  j++;
            //cout<<a[x][j].nr<<"dfdfasd ";
            if(v[a[x][j].nr]==0 )
            {
                poz[x]=j;
                //cout<<j<<" ";
                if(minmuc>a[x][j].c) {minmuc=a[x][j].c; newnod=a[x][j].nr; oldnod=x;}
            }

        }
        v[newnod]=1;
        nod.push_back(newnod);
        suma+=minmuc;
        w.nr=oldnod;
        w.c=newnod;
        sol.push_back(w);
    }
}
int main()
{
    ofstream fout("apm.out");
   Read();
   Salv();
fout<<suma<<"\n"<<sol.size()<<"\n";
for(int i=0; i<sol.size(); i++)
    fout<<sol[i].nr<<" "<<sol[i].c<<"\n";
    return 0;
}