#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,i1,r[500100],P[500100],x,y,val,p,t[500100],node,poz,f[500100],s;
struct edge
{
    int x,y,val;
}v[800100];

bool ord (edge a,edge b)
{
    return a.x<b.x;
}

int main()
{
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>x>>y>>val;
        i1++;
        v[i1].x=x;
        v[i1].y=y;
        v[i1].val=val;
        i1++;
        v[i1].x=y;
        v[i1].y=x;
        v[i1].val=val;
        r[i]=2000000000;
    }
    r[1]=0;

    sort (v+1,v+i1+1,ord);
    m=i1;
    for (int i=1; i<=m; i++)
    if (!P[v[i].x]) P[v[i].x]=i;

    priority_queue<pair<int,int>>Q;
    Q.push(make_pair(0,0));

    while (!Q.empty())
    {
        val=Q.top().first*-1;
        poz=Q.top().second;
        Q.pop();
        if (poz==0) node=1;
        else node=v[poz].y;
        p=P[node];

        while (v[p].x==node)
        {
            if (f[v[p].y]==0)
            {
            Q.push(make_pair(v[p].val*-1,p));
            if (r[v[p].y]>v[p].val) r[v[p].y]=v[p].val,t[v[p].y]=node;


            }


            p++;
        }
        f[node]=1;
    }

    for (int i=1; i<=n; i++) s=s+r[i];
    cout<<s<<'\n';
    cout<<n-1<<'\n';
    for (int i=2; i<=n; i++)
    cout<<i<<" "<<t[i]<<'\n';

    return 0;
}