Lennot

#!/dev/null

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


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

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

for node in graph:
    print "Node", node.id
    for link in node.links:
        print "\tLink", link.target.id


alt = [[[graph[0]], 0]]
paths = []

while alt:
    current = alt.pop()

    if current[0][-1].id == k-1:
        paths.append(current)

    for l in current[0][-1].links:
        if not l.target.id in [i.id for i in current[0]]:
            alt.append([current[0]+[l.target], current[1]+(0 if len(current[0])%2==0 else l.cost)])

paths.sort(key=(lambda q: q[1]))
print paths[-1][1]

"""
4 7
1 2 5
1 4 4
2 3 8
2 1 4
3 1 6
3 4 1
4 2 3
"""

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

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

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED