Тестування випадків
Ви є суддею на конкурсі з програмування і готуєте набір даних для задачі на графи, щоб знайти шлях з мінімальною вартістю. Ви згенерували кілька випадкових випадків, але вони не є цікавими. Ви хочете створити набір даних, відповідь якого буде бажаним значенням, наприклад, число, що представляє цей рік 2010. Тому ви будете коригувати (тобто "налаштовувати") вартість шляху з мінімальною вартістю до заданого значення, змінюючи вартість деяких ребер. Кількість змін має бути якомога меншою.
Задано невід'ємне ціле число c та орієнтований граф G. Кожне ребро G має асоційовану вартість невід'ємного цілого числа. Дано шлях від одного вузла G до іншого, ми можемо визначити вартість шляху як суму вартостей ребер, що складають шлях. Дано пару вузлів у G, ми можемо асоціювати її з невід'ємною вартістю, яка є мінімальною з вартостей шляхів, що їх з'єднують.
Дано граф і пару вузлів у ньому, вам потрібно налаштувати вартості ребер так, щоб шлях з мінімальною вартістю від одного вузла до іншого мав задану цільову вартість c. Ви можете припустити, що c менше за вартість шляху з мінімальною вартістю між заданими вузлами в початковому графі.
Наприклад, на Рисунку 1, мінімальна вартість шляху від вузла 1 до вузла 3 в даному графі дорівнює 6. Щоб налаштувати цю мінімальну вартість до 2, ми можемо змінити вартість ребра від вузла 1 до вузла 3 на 2. Це пряме ребро стає шляхом з мінімальною вартістю після зміни.
Для іншого прикладу, на Рисунку 2, мінімальна вартість шляху від вузла 1 до вузла 12 в даному графі дорівнює 4022. Щоб налаштувати цю мінімальну вартість до 2010, ми можемо змінити вартість ребра від вузла 6 до вузла 12 та одного з шести ребер у правій половині графа. Існує багато можливостей для зміни ребер, але мінімальна кількість змінених ребер дорівнює 2.
Вхідні дані
Вхідні дані є послідовністю наборів даних. Кожен набір даних має такий формат.
n m cf_1 t_1 c_1f_2 t_2 c_2...
f_m t_m c_m
Цілі числа n, m та c є кількістю вузлів, кількістю ребер та цільовою вартістю відповідно, кожне відокремлене одним пробілом, де 2 ≤ n ≤ 100, 1 ≤ m ≤ 1000 та 0 ≤ c ≤ 100000.
Кожен вузол у графі представлений цілим числом від 1 до n.
Наступні m рядків представляють ребра: цілі числа f_i, t_i та c_i (1 ≤ i ≤ m) є вихідним вузлом, вузлом призначення та асоційованою вартістю i-го ребра, кожне відокремлене одним пробілом. Вони задовольняють 1 ≤ f_i, t_i ≤ n та 0 ≤ c_i ≤ 10000. Ви можете припустити, що f_i t_i та (f_i, t_i) (f_j, t_j) коли i j.
Ви можете припустити, що для кожного набору даних існує принаймні один шлях від вузла 1 до вузла n, і що вартість шляху з мінімальною вартістю від вузла 1 до вузла n в даному графі більша за c.
Кінець введення позначається рядком, що містить три нулі, відокремлені одним пробілом.
Вихідні дані
Для кожного набору даних виведіть рядок, що містить мінімальну кількість ребер, вартість яких повинна бути змінена, щоб зробити вартість шляху з мінімальною вартістю від вузла 1 до вузла n рівною цільовій вартості c. Вартість ребер не може бути зроблена від'ємною. Вихід не повинен містити жодних інших зайвих символів.