#include <stdio.h>
#define NMax 305

typedef struct { int ii, jj; } pereche;

int N, M, D[NMax][NMax];
pereche q[NMax * NMax]; int ql, qr;

int main(void)
{
    int i, j, k;
    
    freopen("sate.in", "r", stdin);
    freopen("sate.out", "w", stdout);

    scanf("%d %d", &N, &M);
    for (i = 1; i <= M; i++, ql++)
    {
    	scanf("%d %d", &q[ql].ii, &q[ql].jj);
	scanf("%d", &D[q[ql].ii][q[ql].jj]);
    }

    for (ql--, qr = 0; qr <= ql; qr++)
    {
    	i = q[qr].ii; j = q[qr].jj;

    	for (k = 1; k < i; k++)
            if (D[k][i] && !D[k][j])
		ql++, q[ql].ii = k, q[ql].jj = j, D[k][j] = D[k][i] + D[i][j];

        for (k = i+1; k < j; k++)
        {
        	if (D[i][k] && !D[k][j])
                    ql++, q[ql].ii = k, q[ql].jj = j, D[k][j] = D[i][j] - D[i][k];
		if (D[k][j] && !D[i][k])
                    ql++, q[ql].ii = i, q[ql].jj = k, D[i][k] = D[i][j] - D[k][j];
        }

        for (k = j+1; k < N; k++)
            if (D[j][k] && !D[i][k])
            	ql++, q[ql].ii = i, q[ql].jj = j, D[i][k] = D[i][j] + D[j][k];

        if (D[1][N]) break;
    }

    if (!D[1][N])
    	printf("-1\n");
    else
    	printf("%d\n", D[1][N]);
    
    return 0;
}