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

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