#include <bits/stdc++.h>
using namespace std;

#define maxi 100005
#define INF 1e9

ifstream in("apm.in");
ofstream out("apm.out");
class Graf
{

   int n,m; //n- nr noduri, m- nr muchii
   int x,y; //muchie stg-dr

   int viz[100005]; //pt dfs
   vector<int> *l;
   vector<pair<int,int>> la[50005]; // list adi  pt dij, bell


   public:
       Graf();
       //dfs
       void citireDFS();
       void dfs(int s);
       void nrCompCone();
       //bfs
       int citireBFS();
       void bfs(int s);
       //toposort
       void sort_top_dfs(int s, vector<int>& );
       void citire_top_dfs();
       void sortare_topologica();
       //compTareConexe
       void citire_ctc(vector<int>[],vector<int>[]);
       void dfs1(int s,vector<int>[], vector<int>&,int []);
       void dfs2(int s,vector<int>[], vector<int>[], int [],int);
       void ctc();
        //HAVEL
        void havel_hakimi();
        //PaduriMultDisj
        int find_radacina(int, int[]);
        void unite(int, int, int[], int[]);
        void paduri();
        //dijkstra
        void dijkstra(int[],int[],int);
        void afis_dij();
        //bellmanford
        int bellmanford(int[],int[]);
        void afis_bell();
        //apm
        int apm_find_radacina(int, int[]);
        void apm_unite(int, int, int[], int[]);
        void apm();


};

Graf::Graf() {
    n = m = x = y = 0;
    l = new vector<int>[maxi];
    //l2 = new vector<int>[maxi];
}

//DFS
void Graf::citireDFS()
{
    in>>n>>m;
    int x,y;
    for(int i =0; i<m; i++)
    {
        in>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
}
void Graf::dfs(int s)
{
    viz[s]=1;
    for(auto el:l[s])
    {
        if(viz[el]==0)
        {
            dfs(el);
        }
    }

}

void Graf::nrCompCone()
{
    int c_con=0;
    for(int i=1; i<=n; i++)
    {
        if(viz[i]==0)
        {
            dfs(i);
            c_con++;
        }
    }
    out<<c_con;
}

//BFS
int Graf::citireBFS()
{
    int s;
    in>>n>>m>>s;

    int x,y;
    for(int i =0; i<m; i++)
    {
        in>>x>>y;
        l[x].push_back(y);
    }
    return s;
}

void Graf::bfs(int s)
{

    //int vizitat[10000];
    queue<int> q;
    int dist[100005];
    for(int i =1; i<=n; i++)
    {
        dist[i]=-1;
    }
    int v;
    q.push(s);
    viz[s] = 1;
    dist[s]=0;
    while(!q.empty())
    {

        v=q.front();
        for(auto el:l[v])
        {

            if(dist[el]==-1)
            {
                q.push(el);
                viz[el]=1;
                dist[el]=dist[v]+1;

            }

        }
        q.pop();
    }


    for(int i = 1; i<=n; i++)
    {

        out << dist[i]<<' ';
    }

}

void Graf::citire_top_dfs()
{
    in>>n>>m;
    int x,y;
    for(int i=0;i<m;i++)
    {
        in>>x>>y;
        l[x].push_back(y);
    }
}
void Graf::sort_top_dfs(int s, vector<int> &sortop)
{

    viz[s]=1;
    for(auto el:l[s])
    {
        if(viz[el]==0)
        {
            sort_top_dfs(el, sortop);
        }

    }
    sortop.push_back(s);
}
void Graf::sortare_topologica()
{
       vector <int> sortop;
    for(int i=1; i<=n; i++)
    {
        if(viz[i]==0)
        {
            sort_top_dfs(i, sortop);
        }
    }
    reverse(sortop.begin(),sortop.end());
    for(int i:sortop)
    {
        out<<i<<" ";
    }
}

//CTC
void Graf::citire_ctc(vector<int>graf1[],vector<int>graf2[])
{


    in>>n>>m;
    int x,y;
    for(int i=0;i<m;i++)
    {
        in>>x>>y;
        graf1[x].push_back(y);
        graf2[y].push_back(x);
    }
}
void Graf::dfs1(int s,vector<int>graf1[], vector<int> &sortop, int viz1[])
{


    viz1[s]=1;
    for(auto el:graf1[s])
    {
        if(viz1[el]==0)
        {
            dfs1(el,graf1, sortop,viz1);
        }

    }
    sortop.push_back(s);
}
void Graf::dfs2(int s,vector<int>graf2[], vector<int> comp[], int viz2[],int comp_curenta)
{


    viz2[s] = 1;
    comp[comp_curenta].push_back(s);
    for(auto el:graf2[s])
    {
        if(viz2[el]==0)
        {
            dfs2(el,graf2,comp,viz2,comp_curenta);
        }
    }
}
void Graf::ctc()
{

    int *viz1 = new int [100005];
    int *viz2 = new int [100005];
    for(int i=0; i<100005; ++i)
    {
        viz1[i]=0;
    }
    for(int i=0; i<100005; ++i)
    {
        viz2[i]=0;
    }


    vector <int> *graf1 = new vector<int>[100005];
    vector <int> *graf2 = new vector<int> [100005];
    int comp_curenta=0;
     vector <int> sortop;
     vector <int> *comp = new vector<int> [100005];

    citire_ctc(graf1,graf2);

     for(int i=1; i<=n; i++)
    {

        if(viz1[i]==0)
        {

            dfs1(i,graf1,sortop,viz1);
        }
    }

    reverse(sortop.begin(),sortop.end());

    for(int i:sortop)
    {
        if(viz2[i]==0)
        {

            dfs2(i,graf2,comp,viz2,comp_curenta);
            comp_curenta++;
        }
    }
    out<<comp_curenta<<'\n';
    for(int i=0; i<comp_curenta; i++)
    {
        for(int j = 0; j < comp[i].size(); j++)
        {
            out<<comp[i][j]<<" ";

        }
        out<<'\n';
    }
}

//HAVEL HAKIMI

void Graf::havel_hakimi()
{
    vector <int> v;
    int from, to;
    in>>n;
    int i;
    for(i=0;i<n;i++)
    {
        int w;
        in>>w;
        v.push_back(w);
    }
    sort(v.begin(), v.end());
    for(from = n-1; from>=0; from--)
    {
        for(to = from -1; to >=0; to--)
        {
            if(v[to]>0 && v[from]>0)
            {
                v[from]--;
                v[to]--;

            }
        }
        if(v[from]>0)
        {
            out<<"Nu";
            break;
        }
      sort(v.begin(), v.begin()+from+1);
    }
    out<<"Da";
}

//Paduri de multimi disjuncte

int Graf::find_radacina(int x, int par[])
{
vector <int> met;
    while(x!=par[x])  //parcurgem cat timp x are parinte
       {
            x=par[x];
            met.push_back(x);
       }
    for(auto el:met)
    {
        par[el] = x;
    }
    return x;
}

void Graf::unite(int a, int b, int par[], int dim[])
{
    int x = find_radacina(a,par);
    int y = find_radacina(b,par);
    if(dim[x] > dim[y])         //unim arborele mai mic de arborele mai mare
    {
        par[y] = x;
        dim[x]+=dim[y];
    }
    else
    {
        par[x] = y;
        dim[y] += dim[x];
    }

}

void Graf::paduri()
{
    int *par = new int [100005];   // vector pentru parinti
    int *dim = new int [100005];


    int n, m;
    in>> n >> m;

    for(int i=1; i<=n; i++)
    {
        par[i] = i;
    }

    while (m--)
    {
        int cod, a, b;
        in>> cod >> a >> b;
        if(cod == 1)
        {
            unite(a,b,par,dim);
        }
        else
        {
            if(find_radacina(a,par) == find_radacina(b,par))
                out << "DA\n";

            else
                out << "NU\n";
        }
    }

}

//dijkstra


void Graf::dijkstra(int dist[],int vizi[],int s)
{
    dist[s] = 0;
    priority_queue <pair<int,int>> pq;
    pq.push({0, s});

    while (pq.size())
    {
        int from = pq.top().second;

        pq.pop();
        if(vizi[from])
            continue;
        viz[from] = 1;
        for (auto& per: la[from])
        {
            int to = per.first;
            int cost = per.second;

            if (dist[to] > dist[from] + cost)
            {
                dist[to] = dist[from] + cost;
                pq.push({-dist[to], to});
            }
        }
    }
}


void Graf::afis_dij()
{

    int *dist = new int[50005];
    int *vizi = new int[50005];
    int n,m;
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x,y,d;
        in >> x >> y >> d;
        la[x].push_back({y,d});
    }

    for (int i = 1; i <= n; i++)
        dist[i] = INF;

    dijkstra(dist,viz,1);

    for (int i = 2; i <= n; i++)
    {
        if (INF == dist[i])
            dist[i] = 0;
       out<< dist[i] << ' ';
    }
}

int Graf::bellmanford(int dist[],int vizi[])
{
   dist[1] = 0;
   bool verif =1;
    priority_queue <pair<int,int>> pq;
    pq.push({0, 1});

    while (pq.size())
    {
        int from = pq.top().second;

        vizi[from] ++;
        if(vizi[from] >= n)
        {
            out<< "Ciclu negativ!";
            verif =0;
            break;
        }

        pq.pop();                             //il scoate inainte sa se uite la vecinii lui

        for (auto& per: la[from])
        {
            int to = per.first;
            int cost = per.second;

            if (dist[to] > dist[from] + cost)
            {
                dist[to] = dist[from] + cost;
                pq.push({-dist[to], to});
            }
        }
    }

if(verif==1)
{


    for (int i = 2; i <= n; i++)
    {
        if (INF == dist[i])             //daca nu exista drum se considera distanta 0
            dist[i] = 0;
        out<< dist[i] << ' ';
    }
}
}
void Graf::afis_bell()
{
    int *dist = new int[50005];
    int *vizi = new int[50005];
        in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x,y,d;
        in >> x >> y >> d;
        la[x].push_back({y,d});
    }

    for (int i = 1; i <= n; i++)
        dist[i] = INF;

    bellmanford(dist,vizi);


}
int Graf :: apm_find_radacina(int x, int par[])
{
   vector <int> met;
    while(x!=par[x])  //parcurgem cat timp x are parinte
    {
        x=par[x];
        met.push_back(x);
    }
    for(auto el:met)
    {
        par[el] = x;
    }
    return x;
}
void Graf :: apm_unite(int a, int b, int par[], int dim[])
{
    int x = apm_find_radacina(a,par);
    int y = apm_find_radacina(b,par);
    if(dim[x] > dim[y])         //unim arborele mai mic de arborele mai mare
    {
        par[y] = x;
        dim[x]+=dim[y];
    }
    else
    {
        par[x] = y;
        dim[y] += dim[x];
    }
}
void Graf::apm()
{
    int *par = new int [100005];   // vector pentru parinti
    int *dim = new int [100005]; //cat de multe noduri sunt in arborele respectiv
    vector<pair<int,pair<int,int>>> muchii; // m.first -> costul muchiei, m.second.first -> nodul from, m.second.second -> nodul to
    vector<pair<int,int>> muchii_folosite;

    in>> n >> m;
    while(m--)
    {
        pair<int,pair<int,int>> mc; //muchie curenta
        in>>mc.second.first>>mc.second.second>>mc.first; //muchia curenta a fost citita
        muchii.push_back(mc);      //pune muchia curenta in vectorul mare
    }
    sort(muchii.begin(), muchii.end());
    for(int i=1; i<=n; i++)
    {
        par[i] = i;
    }

    int costTotal = 0;
    for(int m = 0; m < muchii.size(); m++)
    {
        if(apm_find_radacina(muchii[m].second.first,par) != apm_find_radacina(muchii[m].second.second,par))  //daca parintii celor doua noduri sunt diferiti
        {

            costTotal +=  muchii[m].first;
            apm_unite(muchii[m].second.first, muchii[m].second.second,par,dim);    //uneste nodurile

            pair<int,int> p;
            p.first = muchii[m].second.first;
            p.second = muchii[m].second.second;       //pune muchiile folosite in vector
            muchii_folosite.push_back(p);
        }
    }

    out << costTotal<<'\n';
    out<<muchii_folosite.size()<<'\n';
    for(int i=0; i<muchii_folosite.size();i++)
    {

        out<<muchii_folosite[i].first<<" "<<muchii_folosite[i].second<<'\n';
    }
}
int main()
{
    //APM
    Graf g9;
    g9.apm();
    //Bellmanford
    //Graf g8;
    //g8.afis_bell();
    //Dijktra
   // Graf g7;
    //g7.afis_dij();
/* //Paduri
    Graf g6;
    g6.paduri();

    //HAVEL
    Graf g4;
    g4.havel_hakimi();
*/
/*
   //CTC
   Graf g5;
   g5.ctc();
   */
   /*
    //SORTOP

    Graf g3;
    g3.citire_top_dfs();
    g3.sortare_topologica();
    */

   /*
   BFS
    int ss; //stocheaza ce returneaza citirea (nodul s initial)
    Graf g2;
    ss=g2.citireBFS();
    g2.bfs(ss);
   */


    /*
    DFS
    Graf g1;
    g1.citireDFS();

    g1.nrCompCone();
    */
    return 0;
}