/*
 19os Panellinios Diagonismos Pliroforikis - B' fasi
 19th Greek Informatics Contest - 2nd phase

 At an undirected graph the following data are known:

 N: Island multitude: 1 <= N <= 1.000 - Unsigned Short Integer
 M: Course multitude: 1 <= M <= 500.000 - Unsigned Integer
 A, B: Island numbers: 1 <= A < B <= N - Unsigned Short Integer
 K: Course length: 1 <= K <= 1.000.000 - Unsigned Integer

 The algorithm must calculate the 4th-ply (4x) of
 the length of the minimum spanning tree.

 Ch Iossif @ 03 March 2007 under GPL [ http://www.gnu.org/copyleft/gpl.html ]

 Some world wide web resources are:

 http://en.wikipedia.org/wiki/Graph_theory
 http://en.wikipedia.org/wiki/Minimum_spanning_tree
 http://en.wikipedia.org/wiki/Prim's_algorithm
 http://en.wikipedia.org/wiki/Kruskal's_algorithm
 http://www.cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf
 http://www.cs.usask.ca/resources/tutorials/csconcepts/1999_2/tutorial/prim1.html
 http://cprogramming.com/tutorial/computersciencetheory/mst.html

 http://www.math.fau.edu/locke/GRAPHTHE.HTM
 http://www.cs.rhul.ac.uk/books/dbook/
 http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
 http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
 http://www.britannica.com/eb/article-9037754/graph-theory

 This program is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 2
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//#define DEBUG

typedef struct Edge_d {  /* 8 bytes */
    unsigned short int a;  /* 2 bytes */
    unsigned short int b;  /* 2 bytes */
    unsigned int k;        /* 4 bytes */
}
Edge_def;

int Edge_cmp(Edge_def*,Edge_def*);
void Edge_swap(Edge_def*,Edge_def*);
void Incidence_List_qsort(Edge_def*,int,int);

int N, M, sumD;
Edge_def *Incidence_List;


int main(void) {
    unsigned short int nf, *f;
    unsigned int a, b, k, maxdistance, ok;
    register unsigned int i, j;

#if defined DEBUG

    printf("\nReading...\n");
#endif

    if (scanf("%u %u",&N,&M)!=2) {
        printf("N, M values expected.\n");
        exit(1);
    }

    if (N<1 || M<1 || N>1000 || M>500000) {
        printf("N and M values must be in ranges.\n");
        exit(1);
    }

    if ((Incidence_List=malloc(M*sizeof(Edge_def)))==NULL) {
        printf("M value too big. Not enough memory avaliable.\n");
        exit(1);
    }

    for (i=0;i<M;i++) {
        if (scanf("%u %u %u", &a, &b, &k)!=3) {
            printf("A,B and K values expected.\n");
            exit(1);
        }

        if (a<1||b<1||a>N||b>N||k<1||k>1000000) {
            printf("A,B,C triplet values must be in ranges.\n");
            exit(1);
        }

        Incidence_List[i].a=a;
        Incidence_List[i].b=b;
        Incidence_List[i].k=k;
    }

#if defined DEBUG
    printf("\nSorting...\n");
#endif

    Incidence_List_qsort(Incidence_List,0,M-1);

#if defined DEBUG

    printf("\nSorted data:\n");
    printf("%u %u\n", N, M);
    for (i=0;i<M;i++) {
        printf("%u %u %u\n", Incidence_List[i].a, Incidence_List[i].b, Incidence_List[i].k);
    }
#endif

    /* Prim's algorithm */
    nf=0;
    if ((f=malloc(N*sizeof(unsigned short int)))==NULL) {
        printf("N value too big. Not enough memory avaliable.\n");
        exit(1);
    }
    for (i=0;i<N;i++) {
        f[i]=0;
    }

    maxdistance=Incidence_List[M-1].k+1;
    i=0;
    a=Incidence_List[i].a;
    b=Incidence_List[i].b;
    k=Incidence_List[i].k;
    nf=2;
    f[0]=a;
    f[1]=b;
    sumD=4*k;
    Incidence_List[i].k=maxdistance;
    while (N-nf&&sumD>0) {
        for (i=0;i<M && N-nf;i++) {
            a=Incidence_List[i].a;
            b=Incidence_List[i].b;
            if ((k=Incidence_List[i].k)==maxdistance)
                continue;
            for (ok=j=0;j<nf;j++)
                if (f[j]==a||f[j]==b)
                    ok++;
            if (ok==0) {
                if (i==M-1) {
                    sumD=-1;
                    nf=N;
                }
                continue;
            }
            if (ok==2) {
                Incidence_List[i].k=maxdistance;
                continue;
            }
            for (ok=j=0;j<nf;j++)
                if (f[j]==a||f[j]==b)
                    break;
            if (a==f[j]) {
                f[nf++]=b;
            }
            if (b==f[j]) {
                f[nf++]=a;
            }
            sumD+=4*k;
            Incidence_List[i].k=maxdistance;
            break;
        }
    }

    printf("%d\n", sumD);

    return 0;
}

int Edge_cmp(Edge_def *a, Edge_def *b) {
    if (a->k < b->k)
        return 1;
    else
        /*
              if (a->k > b->k)
                return -1;
              else
        */
        return 0;
}

void Edge_swap(Edge_def *a, Edge_def *b) {
    static Edge_def x;

    memcpy(&x,a,sizeof(Edge_def));
    memcpy(a,b,sizeof(Edge_def));
    memcpy(b,&x,sizeof(Edge_def));
}

void Incidence_List_qsort(Edge_def m[], int left, int right) {
    int i, last;

    if (left>=right)
        return;
    Edge_swap( &m[left], &m[(left+right)/2] );
    last=left;
    for(i=left+1;i<=right;i++)
        if( Edge_cmp( &m[i], &m[left] ) )
            Edge_swap( &m[++last], &m[i] );
    Edge_swap( &m[left], &m[last] );
    Incidence_List_qsort(m, left, last-1);
    Incidence_List_qsort(m, last+1, right);
}