#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

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




struct DSU
{

    vector<int> parent,sz;

    DSU(int n)
    {
        for(int i=0;i<=n;i++)
        {parent.push_back(i);
        sz.push_back(1);}
    }

    int origin(int x)
    {
       if(parent[x]==x)
       return x;
       else return parent[x]=origin(parent[x]);
    }



    void join(int a,int b)
    {
        int oa=origin(a);
        int ob=origin(b);
        if(sz[oa]<sz[ob])
        {
            sz[oa]+=sz[ob];
            parent[oa]=ob;
        }
        else
        {
            sz[ob]+=sz[oa];
            parent[ob]=oa;
        }
    }


    bool brothers(int a,int b)
    {
        return origin(a)==origin(b);
    }



};

struct muchie
{
    int x,y,c;


};

 bool cmp(muchie &a,muchie &b)
    {
        return (a.c<b.c);

    }


int main()
{
    int n,m;
    vector<muchie> M;
    vector <int> X,Y;

    muchie c;


    f>>n>>m;
    DSU dsu(n);
    for(int i=0;i<m;i++)
    {
        f>>c.x>>c.y>>c.c;
        M.push_back(c);
    }

    sort(M.begin(),M.end(),cmp);

    int nivel=0,tot=0;

    for(int i=0;i<M.size();i++)
        if(!dsu.brothers(M[i].x,M[i].y))
        {
        dsu.join(M[i].x,M[i].y);
        X.push_back(M[i].x);
        Y.push_back(M[i].y);
        tot+=M[i].c;
        nivel++;
        }


    of<<tot<<endl<<nivel<<endl;
    for(int i=0;i<X.size();i++)
    {
        of<<Y[i]<<' '<<X[i]<<endl;
    }














    return 0;



}