#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

int n,m,lungime_min,p;
int drum[10000][10000],drum2[10000][10000],adia[10000][10000],rang[10000],inceput;

bool exista(){
    int i;
    for(i=1;i<=n;i++)
        if(rang[i]==1) return true;
    return false;
}
void eliminare_noduri(){
    int i,j;
    for(i=1;i<=n;i++)
        if(rang[i]==1)
            for(j=1;j<=n;j++)
                if(adia[i][j]==1){
                    inceput = j;
                    lungime_min+=2*drum2[i][j];
                    adia[i][j] = adia[j][i] = 0;
                    rang[i]-=1;
                    rang[j]-=1;
                }
}
void parc_adancime(int k){
    bool OK;
    int i;
    OK = false;
    for(i=1;i<=n;i++)
    if(adia[k][i]==1){
        if(OK) lungime_min+=drum2[inceput][k];
        lungime_min+=drum2[k][i];
        adia[k][i] = 0;
        OK = true;
        parc_adancime(i);
    }
    if(!OK && k!=inceput) lungime_min +=drum2[inceput][k];

}
void roy_floyd(){
    int i,k,j;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            if(adia[i][k]!= 999999999 && adia[k][j]!=999999999)
                if(drum[i][k]+drum[k][j]< drum[i][j]){
                     drum[i][j] = drum[i][k]+drum[k][j];
                   // cout<<k<<" "<<i<<" "<<j<<" "<<drum[i][j]<<'\n';
                }



}
int main()
{
   ifstream f("traseu.in");
   ofstream g("traseu.out");

    int i,j,a,b,c;

    f>>n>>m;
   //fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            drum[i][j]= drum2[i][j] = 999999999;
    for(i=1;i<=m;i++){
        f>>a>>b>>c;
       // fscanf(f,"%d %d %d",&a,&b,&c);
        adia[a][b] = 1;
        drum[a][b] =  drum[b][a] = drum2[a][b] = drum2[b][a] = c;
        rang[a]++;
        rang[b]++;
    }
    //citirea s-a terminat
    roy_floyd();
    //s-a terminat alcularea distantelor dintre noduri
    inceput = 1;

    while(exista())
        eliminare_noduri();
     //s-a terminat eliminarea nodurilor cu rangul 1. toate nodurile au acum minim 2 conexiuni
    parc_adancime(inceput);
    //fprintf(g,"%d ",lungime_min);
    g<<lungime_min;
    f.close();
    g.close();
    //fclose(f);
    //fclose(g);
    return 0;
}