---

##from functools import *
##
##f = open('23_31518.txt')
##t = { }
##
##for x in f:
##    l, m, w =[float(i) for i in x.split()]
##    if l not in t:
##        t[l]=[ ]
##    t[l].append((m, w))
##    print(t[l])
##@lru_cache(100)
##def f(x, y):
##    if x == y:
##        return 0
##    if x not in t:
##        return 10**10
##    return min(f(m, y)+w for m,w in t[x])
##print(f(1, 100))

##f =open('23_31523.txt')
##t= {}
##
##for x in f:
##    l, m, w = [float(i) for i in x.split()]
##    if l not in t:
##        t[l]= []
##    t[l].append((m, w))
##def f(x,y):
##    if x == y:
##        return 0
##    if x not in t:
##        return 10**10
##    return min(f(m, y)+w for m, w in t[x])
##print(f(3, 97))
    
##f = open('23_31524.txt')
##t = { }
##
##for x in f:
##    l, m, w = [float(i) for i in x.split()]
##    if l not in t:
##        t[l] = []
##    t[l].append((m, w))
##def f(x, y):
##    if x == y:
##        return 0
##    if x not in t:
##        return 10**10
##    return min(f(m, y) + w for m, w in t[x])
##print(f(6, 94))