Route #1: 16 55 70 78 39 109 76 83 86 48 115 36 33 21 91 42 113 82 90 6 34 27 11 111 72 87 40 62 71 96
Route #2: 31 73 67 30 118 9 75 108 47 85 89 51 41 103 17 18 44 28 74 110 19 99 43 49 2 66 97 106 65 79 38
Route #3: 50 94 80 29 32 12 23 14 58 15 7 46 117 5 26 101 105 104 63 95 53 57 100 69 81 4 22 37 92
Route #4: 54 45 8 68 60 59 77 24 1 56 35 102 112 107 116 20 88 52 25 119 84 93 64 98 13 114 3 61 10
Cost 18326