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

using namespace std;

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

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){
                    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){
        lungime_min+=drum2[k][i];
        adia[i][k] = adia[k][i] = 0;
        OK = true;
        parc_adancime(i);
    }
    if(!OK && k!=1) lungime_min +=drum2[1][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()
{
    FILE *f,*g;
    f = fopen("date.in","r");
    g = fopen("date.out","w");

    int i,j,a,b,c;


   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++){
        fscanf(f,"%d %d %d",&a,&b,&c);
        adia[a][b] = adia[b][a] = 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
    while(exista())
        eliminare_noduri();
     //s-a terminat eliminarea nodurilor cu rangul 1. toate nodurile au acum minim 2 conexiuni
    parc_adancime(1);
    cout<<lungime_min;
    fprintf(g,"%d ",lungime_min);

    fclose(f);
    fclose(g);
    return 0;
}