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

#define nmax 200010
#define inf 2000000010
#define mp make_pair
#define pb push_back

int n,m,x,y,c,p[nmax],vec[nmax],poz[nmax],h[nmax],l,nod,lg;
long long s;
vector<pair<int,int> > g[nmax],r;

void push(int x)
{
    while ((x*2<=l && p[h[x]]>p[h[x*2]]) || (x*2+1<=l && p[h[x]]>p[h[x*2+1]]))
    {
        if (p[h[x*2]]<p[h[x*2+1]] || x*2+1>l)
        {
            swap(h[x],h[x*2]);
            swap(poz[h[x]],poz[h[x*2]]);
            x*=2;
        }
        else
        {
            swap(h[x],h[x*2+1]);
            swap(poz[h[x]],poz[h[x*2+1]]);
            x=x*2+1;
        }
    }
}

void pop(int x)
{
    while (x>1 && p[h[x]]<p[h[x/2]])
    {
        swap(h[x],h[x/2]);
        swap(poz[h[x]],poz[h[x/2]]);
        x/=2;
    }
}

int sheap()
{
    x=h[1];
    swap(h[1],h[l]);
    swap(poz[h[1]],poz[h[l]]);
    l--;
    push(1);
    poz[x]=0;
    return x;
}

void apm(int x)
{
    int i,lg,nod,cost;
    lg=g[x].size();
    for (i=0;i<lg;i++)
    {
        nod=g[x][i].first;
        cost=g[x][i].second;
        p[nod]=min(p[nod],cost);
        if (p[nod]==cost)
            vec[nod]=x;
    }
}

void heap(int x)
{
    h[++l]=x;
    poz[x]=l;
    pop(l);
}

int main()
{
    int i,j;
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        g[x].pb(mp(y,c));
        g[y].pb(mp(x,c));
    }
    for (i=2;i<=n;i++)
        p[i]=inf;
    apm(1);
    for (i=2;i<=n;i++)
        heap(i);
    for (i=2;i<=n;i++)
    {
        x=sheap();
        apm(x);
        s+=p[x];
        r.pb(mp(x,vec[x]));
        lg=g[x].size();
        for (j=0;j<lg;j++)
        {
            nod=g[x][j].first;
            if (poz[nod])
                pop(poz[nod]);
        }
    }
    cout<<s<<'\n'<<n-1<<'\n';
    lg=r.size();
    for (i=0;i<lg;i++)
        cout<<r[i].first<<" "<<r[i].second<<'\n';
}