#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

struct muchie{
   
   int x,y,cst;
   
}mc;

bool cmp(muchie a,muchie b)
{
    if(a.cst<b.cst)
       return true;
    else
        return false;
}

vector<muchie> M;
vector<int> varb;
vector<int>::iterator it;
int T[200008];
int main()
{
    FILE *f,*g;
    int i,n,m,a,b,ct,cost,p,j;
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&ct);
        mc.x=a; mc.y=b; mc.cst=ct;
        M.push_back(mc);
    }
    fclose(f);
    sort(M.begin(),M.end(),cmp);
    
    cost=M[0].cst;
    T[M[0].x]=0;
    T[M[0].y]=M[0].x;
    
    varb.push_back(M[0].x);
    varb.push_back(M[0].y);
    M.erase(M.begin());
    
    while(varb.size()!=n)
    {
        for(i=0;i<M.size();i++)
            for(it=varb.begin();it!=varb.end();++it)
               if(M[i].x==*it&&T[M[i].y]==0)
                {
                     p=M[i].y;
                     goto gata;
                } 
               else
                  if(M[i].y==*it&&T[M[i].x]==0)
                {
                    p=M[i].x;
                    goto gata;
                }
        gata:       
        varb.push_back(p);
        cost=cost+M[i].cst;
        T[p]=*it; 
        M.erase(M.begin()+i);                           
    }
    for(i=1;i<=n;i++)
        cout<<T[i]<<" ";
    fprintf(g,"%d%\n%d\n",cost,n-1);
    for(i=1;i<=n;i++)
        if(T[i]!=0)
          fprintf(g,"%d %d\n",T[i],i);
    fclose(g);
    return 0;
}