#include <fstream>
#include <vector>
using namespace std;
ifstream in ("apm.in");
ofstream out("apm.out");
int const N=200005;
int const INF=1005;

int n,m,VEC[N],cArb,cost[N];
vector <pair<int,int> > d[N];
vector <pair<int,int> > dArb;


class heap
{
    int length;
    int H[N],POZ[N];
    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(cost[H[index]]>cost[H[left]])
            minIndex = left;
        if((right<=length)&&(cost[H[minIndex]]>cost[H[right]]))
            minIndex = right;
        if(minIndex != index)
        {
            //need to swap
            swap(H[index],H[minIndex]);
            swap(POZ[H[index]],POZ[H[minIndex]]);
            BubbleDown(minIndex);
        }
    }
public:
    int getPoz(int x)
    {return POZ[x];}
    void BubbleUp(int index)
    {
        while(index > 1 && cost[H[index]] < cost[H[index / 2]])
        {
            swap(H[index],H[index / 2]);
            swap(POZ[H[index]],POZ[H[index / 2]]);
            index/=2;
        }
    }
    void add(int nod)
    {
        H[++length] = nod;
        POZ[nod] = length;
        BubbleUp(length);
    }
    int pop()
    {
        int x = H[1];
        swap(H[1],H[length]);
        swap(POZ[H[1]],POZ[H[length]]);
        length--;
        BubbleDown(1);
            POZ[x] = 0;
        return x;
    }
}h;
void add_to_apm(int x)
{
    for(size_t i=0;i<d[x].size();i++)
    {
        int nod = d[x][i].first;
        int cst = d[x][i].second;
        if(cst<=cost[nod])
        {
            cost[nod]=cst;
            VEC[nod]=x;
        }
    }
}
int main()
{
    in>>n>>m;
    for(int i=2;i<=n;i++)
        cost[i]=INF;
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        in>>x>>y>>c;
        d[x].push_back(make_pair(y,c));
        d[y].push_back(make_pair(x,c));
    }
    add_to_apm(1);
    for(int i=2;i<=n;i++)
        h.add(i);
    for(int i=1;i<n;i++)
    {
        int x=h.pop();
        add_to_apm(x);
        cArb += cost[x];
        dArb.push_back(make_pair(x,VEC[x]));
        for(size_t j=0;j<d[x].size();j++)
        {
            int nod=d[x][j].first;
            if (h.getPoz(nod)) h.BubbleUp(h.getPoz(nod));
        }
    }
    out<<cArb<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;i++)
        out<<dArb[i].first<<" "<<dArb[i].second<<"\n";
    return 0;
}