Lennot

#!/dev/null

class Node:
    def __init__(self, nid, l):
        self.id = nid
        self.links = l
class Link:
    def __init__(self, target, cost=0):
        self.target = target
        self.cost = cost

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()])

graph = [Node(q, []) for q in range(k)]
for q in y:
    graph[q[0]-1].links.append(Link(graph[q[1]-1], q[2]))


def search(source, target, path=[], cost=0):
    path += [source.id]
    if id(source) == id(target):
        return True, cost
    ret = []
    for link in source.links:
        if path.count(link.target.id)>2:
            continue
        if cost+link.cost*(len(path)%2) < min(ret+[float("inf")]):
            x,r = search(link.target, target, path[:], cost+link.cost*(len(path)%2))
            if x:
                ret.append(r)
    if len(ret):
        return True, min(ret)
    return False, 0

print search(graph[0], graph[-1])[1]


"""

5 7
1 2 2
2 3 1
2 4 1
2 5 8
3 1 3
3 4 4
4 5 3



4 6
1 2 2
1 3 2
1 4 10
2 1 2
3 2 1
3 4 2


4 4
1 2 1
2 3 1
3 1 1
3 4 100


"""

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

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: RUNTIME ERROR

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED