/*#include "stdafx.h"
#include "infoarena.h"

#include <conio.h>/**/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define _TRASEU_
#ifdef _TRASEU_

#ifndef _INC_CONIO
void clrscr()
{
    freopen("traseu.out", "w", stdout);
}
void getch() {}
#else
void clrscr() {}
#endif

#define rep(i,n) for(i=0;i<n;i++)
#define min(a,b) (((a) < (b)) ? (a) : (b))

int a[60][60], b[60][60], c[60][60];
int el[2000][2], xe[2000];
int n, m;
const int INF = 36000001;

void printall()
{
    int i,j;
    rep(i,n){ rep(j,n) printf("%2d ", a[i][j] != INF ? a[i][j] : 0); printf("\n"); }
}

int goroute(int x, int y)
{
    int z, o = 0;
    //printf("%d ", x+1);
    while (x!=y)
    {
        z = c[x][y];
        o += a[x][z];
        xe[b[x][z]-1] = 1;
        x = z;
        //printf("%d ", x+1);
    }
    //printf("\n");
    return o;
}

int main()
{
    int i,j,k;
    clrscr();
    FILE *fin = fopen("traseu.in", "r");
    fscanf(fin, "%d %d", &n, &m);
    rep(i,n) rep(j, n) a[i][j] = INF;
    rep(i,m)
    {
        int x,y,z;
        fscanf(fin, "%d %d %d", &x,&y,&z);
        a[x-1][y-1] = z;
        b[x-1][y-1] = i+1;
        c[x-1][y-1] = y-1;
        el[i][0] = x-1; el[i][1] = y-1;
    }

    rep(k,n) rep(i,n) rep(j,n)
    {
        if (a[i][j] > a[i][k] + a[k][j])
        {
            a[i][j] = a[i][k] + a[k][j];
            c[i][j] = c[i][k];
        }
    }

    int ossz = 0;

    rep(j, n) if (b[0][j])
    {
        //printf("1 ");
        ossz += a[0][j] + goroute(j, 0);
        xe[b[0][j]-1] = 1;
    }

    rep(i, m) if (!xe[i])
    {
        ossz += goroute(0, el[i][0]);
        ossz += goroute(el[i][0], el[i][1]);
        ossz += goroute(el[i][1], 0);
    }

    //printall();
    printf("%d", ossz);
    

    getch();
    return 0;
}

#endif