#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];

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 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 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=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=2;i<=n;i++)
        cost[i]=INF;
    add_to_apm(1);
    for(int i = 2;i <= n; ++i)
        h.add(i);
    for(int i = 1;i < n; ++i)
    {
        int x = h.scoate_radacina_heap();
        add_to_apm(x);
        ANS += cost[x];
        VANS.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<<ANS<<"\n"<<n-1<<"\n";
    //for(size_t i=0;i<n-1;i++)
        //out<<VANS[i].first<<" "<<VANS[i].second<<"\n";
    for(int i=2;i<=n;i++)
        out<<i<<" "<<VEC[i]<<"\n";
    return 0;
}