#include <stdio.h>


#define nmax 61
#define inf 1<<30
long C[nmax];
typedef struct nod
 {
 int x,c;
 nod *urm;
 }graf;
graf *G[nmax];
int n,k,Q[nmax],cs[nmax];
void add(graf *&g,int x,int c)
 {
 graf *p=new graf;
 p->x=x;
 p->c=c;
 p->urm=g;
 g=p;
 }
void read()
 {
 FILE *f=fopen("traseu.in","r");
 int m,x,y,c,i;
 fscanf(f,"%d %d",&n,&m);
 for(i=1;i<=m;i++)
  {
  fscanf(f,"%d %d %d",&x,&y,&c);
  add(G[x],y,c);
  if(y==1)
   {
   Q[++k]=x;
   cs[Q[k]]=c;
   }
  }
 fclose(f);
 }
void BF()
 {
 int Co[nmax],cd=0,i,x;
 C[1]=0;
 for(i=2;i<=n;i++)  C[i]=inf;
 for(graf *g=G[1];g!=NULL;g=g->urm)
  {
  C[g->x]=g->c;
  Co[++cd]=g->x;
  }
 for(i=1;i<=cd;i++)
  {
  x=Co[i];
  for(graf *g=G[x];g!=NULL;g=g->urm)
   {
   if(C[g->x]>C[x]+g->c)
    {
    C[g->x]=C[x]+g->c;
    Co[++cd]=g->x;
    }
   }
  }
 }
void solve()
 {
 BF();
 int i;
 long cost=0;
 for(i=1;i<=k;i++)
  {
  cost+=C[Q[i]]+cs[Q[i]];
  }
 FILE *g=fopen("traseu.out","w");
 fprintf(g,"%ld",cost);
 fclose(g);
 }
int main()
 {
 read();
 solve();
 return 0;
 }