Lennot

#!/bin/slow/python

k, l = [int(i) for i in raw_input().split()]
y = []
for q in range(l):
    y.append([int(i) for i in raw_input().split()])


def all_paths(current, target, path=[]):
    path = path + [current]
    if current == target:
        return path
    p = [q for q in y if q[0]==current]
    pp = []
    for q in p:
        if q[1] in path:
            continue
        x = all_paths(q[1], target, path)
        if x:
            pp.append(x)
    return pp
def twodimensionate(L):
    if all([type(q)!=type([]) for q in L]):
        return [L]
    r = []
    for l in L:
        r+=twodimensionate(l)
    return r
def getprices(x):
    return [sum([[e for e in y if e[:2]==q[w:w+2]][0][2] for w in range(len(q)-1)][::2]) for q in x]
    #return [[q[w:w+2]+[[e for e in y if e[:2]==q[w:w+2]][0][2]] for w in range(len(q)-1)] for q in x]



paths = twodimensionate(all_paths(1, k))
prcs = getprices(paths)
print min(prcs)




"""
5 12
1 2 0
1 3 0
1 4 0
1 5 0
2 3 0
2 4 0
2 5 0
3 4 0
3 5 0
3 1 0
4 1 0
4 5 0

"""

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED