#include <fstream>
#include <vector>
using namespace std;
ifstream in ("apm.in");
ofstream out("apm.out");

struct muchie{int x,y,c;};
vector <pair<int,int> > dArb;
int const N=200005;
int n,m,p[N],h[N],cArb;

class heap
{
    int length;
    muchie H[N];
public:
    int getLength()
    {return length;}
    void BubbleDown(int index)
    {
        int left=2*index;
        int right=2*index+1;
        if(left>length)
            return; //index is a leaf
        int minIndex=index;
        if(H[index].c>H[left].c)
            minIndex = left;
        if((right<=length)&&(H[minIndex].c>H[right].c))
            minIndex = right;
        if(minIndex != index)
        {
            //need to swap
            swap(H[index],H[minIndex]);
            BubbleDown(minIndex);
        }
    }
    void BubbleUp(int index)
    {
        while(index > 1 && H[index].c<H[index/2].c)
        {
            swap(H[index],H[index / 2]);
            index/=2;
        }
    }
    void add(muchie m)
    {H[++length]=m;}
    void push(muchie m)
    {
        H[++length]=m;
        BubbleUp(length);
    }
    muchie pop()
    {
        muchie m = H[1];
        swap(H[1],H[length]);
        length--;
        BubbleDown(1);
        return m;
    }
}HP;

void MakeSet(int u)
{
    p[u]=h[u]=0;
}
int FindSet(int u)
{
    if(p[u]==0)
        return u;
    p[u]=FindSet(p[u]); //tatal lui u devine radacina
        return p[u];
}
void Union(int u,int v)
{
    u=FindSet(u);
    v=FindSet(v);
    if (h[u]>h[v])
        p[v]=u;
    else
    {
        p[u]=v;
        if(h[u]==h[v])
            h[v]=h[v]+1;
    }
}

int main()
{
    in>>n>>m;
    for(int i=0;i<m;i++)
    {
        muchie nou;
        in>>nou.x>>nou.y>>nou.c;
        HP.add(nou);
    }
    for(int i=HP.getLength()/2; i>0;i--)
        HP.BubbleDown(i);
    for(int i=1;i<=n;i++)
        MakeSet(i);
    while(HP.getLength()>1)
    {
        muchie mch=HP.pop();
        if(FindSet(mch.x)!=FindSet(mch.y))
           {
                dArb.push_back(make_pair(mch.x,mch.y));
                cArb+=mch.c;
                Union(mch.x,mch.y);
                if(dArb.size()==n-1)
                    break;
            }
    }
    out<<cArb<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;i++)
        out<<dArb[i].first<<" "<<dArb[i].second<<"\n";
    return 0;
}