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

int VEC[N],ANS,cost[N];
vector <pair<int,int> > d[N],VANS;
int n,m,C[N];

struct heap
{
    int length;
    int H[2*N],POZ[N];

    void BubbleDown(int index)
    {
        int left=2*index+1;
        int right=2*index+2;
        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);
        }

        /*while((poz * 2 <= L && cost[H[poz]] > cost[H[poz * 2]]) || (poz * 2 + 1 <= L && cost[H[poz]] > cost[H[poz * 2 + 1]]))
        {
            if (cost[H[poz * 2]] < cost[H[poz * 2 + 1]] || poz * 2 + 1 > L)
            {
                swap(H[poz],H[poz * 2]);
                swap(POZ[H[poz]],POZ[H[poz * 2]]);
                poz *= 2;
            }
            else
            {
                swap(H[poz],H[poz * 2 + 1]);
                swap(POZ[H[poz]],POZ[H[poz * 2 + 1]]);
                poz = poz * 2 + 1;
            }
        }*/
    }
    void pop(int poz)
    {
        while(poz > 1 && cost[H[poz]] < cost[H[poz / 2]])
        {
            swap(H[poz],H[poz / 2]);
            swap(POZ[H[poz]],POZ[H[poz / 2]]);
            poz = poz / 2;
        }
    }
    void introduce_in_heap(int nod)
    {
        H[++length] = nod;
        POZ[nod] = length;
        pop(length);
    }
    int scoate_radacina_heap()
    {
        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 introduce_in_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;
        cost[nod] = min(cost[nod],cst);
        if (cost[nod] == cst) VEC[nod] = x;
    }
}

int main()
{
    in>>n>>m;
    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));
    }

    for(int i = 1;i <= n; ++i) cost[i] = INF;
    cost[1] = 0;
    introduce_in_apm(1);
    for(int i = 2;i <= n; ++i)
    {
        h.introduce_in_heap(i);
    }
    for(int i = 1;i < n; ++i)
    {
        int x = h.scoate_radacina_heap();
        introduce_in_apm(x);
        ANS += cost[x];
        VANS.push_back(make_pair(x,VEC[x]));
        for(unsigned int j = 0;j < d[x].size(); ++j)
        {
            int nod = d[x][j].first;
            if (h.POZ[nod]) h.pop(h.POZ[nod]);
        }
    }
    out<<ANS<<"\n"<<n-1<<"\n";
    for(size_t i=0;i<n-1;i++)
        out<<VANS[i].first<<" "<<VANS[i].second<<"\n";
    return 0;
}