Святковий торт

Обмеження: 2 сек., 256 МіБ

Петро, 53 роки, кондитер, вирішив спеціально до свята 47-го дня року спекти торт. Причому, зважаючи на масштаби святкування цієї визначної події у Львові, Петро планує спекти багато тортів і деякі з них з’єднати вафельними мостиками. Подейкують, що в композиції також буде декілька шоколадних фонтанів.

Згідно плану, всього повинно бути $n$ тортів, сполучених $m$ двосторонніми мостами. Проте Петро ще остаточно не вирішив якими будуть довжини мостiв: для деяких мостів він вже знає довжину, а для інших ще вагається.

Петро вірить, що святкування вийде особливо успішним, якщо найкоротша відстань між тортом з номером 1 і тортом з номером $n$ по мостах буде рівна $w$. Допоможіть йому визначити довжини мостiв, які б задовольняли бажаній умові. У випадку успіху Петро пригостить вас своїми солодощами.

Вхідні дані

У першому рядку задано три цілі числа $n$, $m$, $w$ — кількість тортів, кількість мостів і бажана відстань відповідно.

У наступних $m$ рядках задано по три цілі числа $u_i$, $v_i$, $w_i$. Це означає, що $i$-й міст сполучає торти з номерами $u_i$ і $v_i$ і має довжину $w_i$. Причому якщо $w_i = -1$, то довжина цього моста ще не відома.

Гарантовано iснує шлях по мостах між будь-якою парою тортів, а також жоден міст не сполучає торт з самим собою.

Вихідні дані

Виведіть $m$ рядків, по одному цілому числу в кожному — довжини мостiв у тому порядку, в якому вони задані у вхiдних даних.

У випадку, якщо бажаної мінімальної відстані досягнути неможливо, виведіть -1 у єдиному рядку.

Зверніть увагу, що кожен міст повинен мати цілу додатну довжину в межах від 1 до 200.

Обмеження

$1 \le n \le 100$,

$1 \le u_i, v_i \le n$, $u_i \neq v_i$,

$1 \le m, w \le 200$,

$w_i = -1$ або $1 \le w_i \le 200$,

у 10-ти тестах усі мости початково не мають довжини.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 4 11 1 2 4 1 3 -1 2 4 -1 3 4 7	4 4 47 7

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 2 4 1 2 -1 2 3 4	-1