#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct {
    int x,y,cost;
}rez[200005],muchii[400005];
int heap[400005],n,m,a,b,c,l,fr[200005],where[400005],rez_cost,k;
int start,inf=(1<<30),d,mn,ch=0;
vector< pair<int,int> >vecini[200005];
vector<int> p[200005];
string s;

int nextint()
{
    int num=0;
    bool ok=true;
    while(s[ch]==' ') ++ch;
    if(s[ch]=='-') ok=false, ++ch;
    while(s[ch]<='9' && s[ch]>='0')
    {
        num=num*10+s[ch]-'0';
        ++ch;
    }
    if(!ok) num=-num;
    return num;
}

void up(int poz)
{
    while(poz>1 && muchii[heap[poz]].cost<muchii[heap[poz/2]].cost)
    {
        swap(where[heap[poz]],where[heap[poz/2]]);
        swap(heap[poz],heap[poz/2]);
        poz/=2;
    }
}

void down(int poz)
{
    bool ok=true;
    while(ok)
    {
        ok=false;
        mn=inf;
        if(poz*2<=l && muchii[heap[poz*2]].cost<mn) mn=muchii[heap[poz*2]].cost, d=poz*2;
        if(poz*2+1<=l && muchii[heap[poz*2+1]].cost<mn) mn=muchii[heap[poz*2+1]].cost, d=poz*2+1;
        if(mn<muchii[heap[poz]].cost)
        {
            ok=true;
            swap(where[heap[poz]],where[heap[d]]);
            swap(heap[poz],heap[d]);
            poz=d;
        }
    }
}

void adauga()
{
    //nod nou in subgraf
    if(fr[muchii[heap[1]].x]==0)
    {
        fr[muchii[heap[1]].x]=1;
        start=muchii[heap[1]].x;
    }
    else
    {
        fr[muchii[heap[1]].y]=1;
        start=muchii[heap[1]].y;
    }
    rez_cost+=muchii[heap[1]].cost;
    rez[++k].x=muchii[heap[1]].x; rez[k].y=muchii[heap[1]].y;

    //muchii noi
    for(int i=0;i<vecini[start].size();++i)
    {
        if(fr[vecini[start][i].first]==0)
        {
            ++l;
            heap[l]=p[start][i];
            where[p[start][i]]=l;
            up(l);
        }
    }
}

bool cond()
{
    return(fr[muchii[heap[1]].x]==1 && fr[muchii[heap[1]].y]==1);
}

void scoate()
{
    heap[1]=heap[l];
    where[heap[1]]=1;
    --l;
    down(1);
}

void elimina()
{
    while(k<n-1)
    {
        adauga();
        while(cond()) scoate();
    }
}

int main()
{
    f>>n>>m; getline(f,s);
    heap[0]=(1<<30);
    for(int i=1;i<=m;++i)
    {
        getline(f,s); ch=0;
        a=nextint();
        b=nextint();
        c=nextint();
        vecini[a].push_back(make_pair(b,c));
        vecini[b].push_back(make_pair(a,c));
        p[a].push_back(i);
        p[b].push_back(i);
        muchii[i].x=a; muchii[i].y=b; muchii[i].cost=c;
    }
    fr[1]=1;
    for(int i=0;i<vecini[1].size();++i)
    {
        ++l;
        heap[l]=p[1][i];
        where[p[1][i]]=l;
        up(l);
    }
    elimina();
    g<<rez_cost<<'\n'<<k<<'\n';
    for(int i=1;i<=k;++i)
    {
        g<<rez[i].x<<' '<<rez[i].y<<'\n';
    }
    return 0;
}