#include <cstdio>
#include <vector>
#define NMAX 200023
#define LIM 100000003
int n,m;
using namespace std;
struct str
{
    int nod;
    int val;
}a[NMAX];
int sol[NMAX],tt[NMAX],vis[NMAX],unde[NMAX];
int nt=1;
vector<int>adj[NMAX],cst[NMAX];
int stanga(int x)
{
    return 2*x;
}
int dreapta(int x)
{
    return 2*x+1;
}
int tata(int x)
{
    return x/2;
}
void checkup(int pos)
{
    while(1)
    {
        int t=tata(pos);
        if(t==0) return;
        if(a[t].val>a[pos].val)
        {
            swap(a[t].nod,a[pos].nod);
            swap(a[t].val,a[pos].val);
            swap(unde[a[t].nod],unde[a[pos].nod]);
            pos=t;
        }
        else return;
    }
}
void checkdown(int pos)
{
    while(1)
    {
        int mini=a[pos].val,caz=0;
        int s=stanga(pos);
        if(s<=nt&&mini>a[s].val)
        {
            mini=a[s].val;
            caz=1;
        }
        int dr=dreapta(pos);
        if(dr<=nt&&mini>a[dr].val)
        {
            mini=a[dr].val;
            caz=2;
        }
        if(caz==0) break;
        else if(caz==1)
        {
            swap(a[s].nod,a[pos].nod);
            swap(a[s].val,a[pos].val);
            swap(unde[a[s].nod],unde[a[pos].nod]);
            pos=s;
        }
        else
        {
            swap(a[dr].nod,a[pos].nod);
            swap(a[dr].val,a[pos].val);
            swap(unde[a[dr].nod],unde[a[pos].nod]);
            pos=dr;
        }
    }
}
void rem()
{
    swap(a[1].nod,a[nt].nod);
    swap(a[1].val,a[nt].val);
    swap(unde[a[1].nod],unde[a[nt].nod]);
    nt--;
    checkdown(1);
}
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x1,x2,cttx;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x1,&x2,&cttx);
        adj[x1].push_back(x2);
        cst[x1].push_back(cttx);
        adj[x2].push_back(x1);
        cst[x2].push_back(cttx);
    }
    sol[1]=0;
    a[1].nod=1;
    a[1].val=sol[1];
    unde[1]=1;
    for(int i=2;i<=n;i++)
    {
        ++nt;
        sol[i]=LIM;
        a[i].nod=i;
        a[i].val=sol[i];
        unde[i]=nt;
    }
    vector<int>::iterator it1,it2;
    for(int i=1;i<=n;i++)
    {
        int best=a[1].nod;
        vis[best]=1;
        rem();
        for(it1=adj[best].begin(),it2=cst[best].begin();it1!=adj[best].end();++it1,++it2)
        {
            if(sol[*it1]>*it2&&vis[*it1]==0)
            {
                sol[*it1]=*it2;
                a[unde[*it1]].val=*it2;
            //    printf("%d %d\n",nt,unde[*it1]);
                checkup(unde[*it1]);
                tt[*it1]=best;
            }
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++) sum+=sol[i];
    printf("%d\n%d\n",sum,n-1);
    for(int i=2;i<=n;i++) printf("%d %d\n",i,tt[i]);
}