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

Limits: 2 sec., 256 MiB

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

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

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

Input

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

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

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

Output

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

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

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

Constraints

$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-ти тестах усі мости початково не мають довжини.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 4 11 1 2 4 1 3 -1 2 4 -1 3 4 7	4 4 47 7

Input (stdin) сopy	Output (stdout) сopy
3 2 4 1 2 -1 2 3 4	-1