---

from functools import *
import sys
sys.setrecursionlimit(10**8)
#1
d={}
for s in open('23_31608.txt'):
    l, m, w = map(float, s.split())
    d[int(l)]=d.get(int(l), []) + [[int(m), float(w)]]
@lru_cache(None)
def f(v):
    if v==38:
        return (0,0)
    if v not in d:
        return (10**10,10**10)
    return min((x[1]+f(x[0])[0], f(x[0])[1]+1) for x in d[v])
print(f(113))

#2
d={}
for s in open('23_31618.txt'):
    l, m, w = map(float, s.split())
    d[int(l)]=d.get(int(l), []) + [[int(m), float(w)]]
@lru_cache(None)
def f(v):
    if v==100:
        return (0,0)
    if v not in d:
        return (-10**10,-10**10)
    return max((x[1]+f(x[0])[0], f(x[0])[1]+1) for x in d[v])
print(f(1))

#3
d={}
for s in open('23_31619.txt'):
    l, m, w = map(float, s.split())
    d[int(l)]=d.get(int(l), []) + [[int(m), float(w)]]
@lru_cache(None)
def f(v, k):
    if v==k:
        return (0,0)
    if v not in d:
        return (10**10,10**10)
    return min((x[1]+f(x[0],k)[0], f(x[0],k)[1]+1) for x in d[v])
print(f(113, 180)[0]+f(180, 316)[0])


#4
d={}
for s in open('23_31620.txt'):
    l, m, w = map(float, s.split())
    d[int(l)]=d.get(int(l), []) + [[int(m), float(w)]]
@lru_cache(None)
def f(v, k):
    if v==k:
        return (0,0)
    if v not in d or v==96:
        return (10**10,10**10)
    return min((x[1]+f(x[0],k)[0], f(x[0],k)[1]+1) for x in d[v])
print(f(173,238))



#5
d={}
for s in open('23_31621.txt'):
    l, m, w = map(float, s.split())
    d[int(l)]=d.get(int(l), []) + [[int(m), float(w)]]
@lru_cache(None)
def f(v, k):
    if v==k:
        return (0,0)
    if v not in d:
        return (10**10,10**10)
    return min((x[1]+f(x[0],k)[0], f(x[0],k)[1]+1) for x in d[v])
print(f(354,312)[0]+f(312, 46)[0]+f(46, 412)[0])



#6
d={}
for s in open('23_31623.txt'):
    l, m, w = map(float, s.split())
    d[int(l)]=d.get(int(l), []) + [[int(m), float(w)]]
@lru_cache(None)
def f(v, k):
    if v==k:
        return (0,0)
    if v not in d:
        return (10**10,10**10)
    return min((x[1]+f(x[0],k)[0], f(x[0],k)[1]+1) for x in d[v])
print(f(173,91)[0]+f(91, 474)[0]+f(474, 523)[0])



#7
d={}
for s in open('23_32027.txt'):
    l, m, w = map(float, s.split())
    d[int(l)]=d.get(int(l), []) + [[int(m), float(w)]]
@lru_cache(None)
def f(v, k):
    if v==k:
        return (0,0)
    if v not in d or v==96:
        return (10**10,10**10)
    return min((x[1]+f(x[0],k)[0], f(x[0],k)[1]+1) for x in d[v])
print(f(4,400)[0]+f(400, 298)[0])




#8
d = {}
for line in open('23_31566.txt'):
    l, m, w = line.split()
    d[int(l)] = d.get(int(l), []) + [(int(m), float(w))]
@lru_cache(None)
def f(v):
    if v == 8318:
        return 0
    if v not in d:
        return 10**10
    return min(1 + f(to) for to, w in d[v])
print(int(f(402)))



#9
from functools import *
d = {}
for line in open('23_31577.txt'):
    l, m, w = line.split()
    d[int(l)] = d.get(int(l), []) + [(int(m), float(w))]
@lru_cache(None)
def f(v):
    if v == 82:
        return 0
    if v not in d:
        return -10**10
    return max(1 + f(to) for to, w in d[v])
print(int(f(15)))




#10
d={}
for s in open('23_31567.txt'):
    l, m, w = map(float, s.split())
    d[int(l)]=d.get(int(l), []) + [[int(m), float(w)]]
@lru_cache(None)
def f(v, k):
    if v==k:
        return (0,0)
    if v not in d:
        return (10**10,10**10)
    return min((f(x[0],k)[0]+1, x[1]+f(x[0],k)[1]) for x in d[v])
print(f(102, 2616))