В стране Берляндии есть $$$n$$$ городов и $$$m$$$ двунаправленных дорог между ними. Все города пронумерованы от $$$1$$$ до $$$n$$$, и из любого города страны возможно добраться до любого другого. Между любой парой городов есть не более одной дороги, при этом каждая дорога имеет целую положительную длину.
Внутри страны находятся $$$2$$$ княжества, которые хотят разделить территорию между собой. Столица первого княжества находится в городе с номером $$$a$$$, а столица второго — в городе с номером $$$b$$$.
Княжества не очень ладят между собой, поэтому также хотят, чтобы между ними обязательно была граница, состоящая из непустого множества городов, не принадлежащих ни одному из княжеств.
Определите, можно ли разделить территорию так, чтобы одновременно выполнялись $$$4$$$ следующих условия:
- если кратчайшее расстояние от некоторого города $$$x$$$ до $$$a$$$ и $$$b$$$ одинаково, то он находится на границе и не принадлежит никакому из княжеств;
- если кратчайшее расстояние от некоторого города $$$x$$$ до $$$а$$$ меньше, чем до $$$b$$$, он принадлежит $$$1$$$-му княжеству;
- если первые $$$2$$$ условия не верны, город $$$x$$$ принадлежит $$$2$$$-му княжеству;
- нельзя пройти из одного княжества в другое, не пересекая граничный город;
Например, пусть $$$n = 7$$$, $$$m = 9$$$, столица первого княжества находится в городе $$$2$$$, а второго — в городе $$$3$$$. Карта Берляндии выглядит как на рисунке ниже:
Все города, которые будут принадлежать первому княжеству, покрашены в красный цвет, второму — в зеленый. Города, которые будут находиться на границе, покрашены в серый.
Первая строка входных данных содержит два целых числа $$$n$$$, $$$m$$$ ($$$3 \le n \le 500$$$, $$$n - 1 \le m \le \frac{n \cdot (n - 1)}{2}$$$) — количество городов в Берляндии и количество дорог между ними.
В следующих $$$m$$$ строках находится по три целых положительных числа $$$u$$$, $$$v$$$, $$$c$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$, $$$1 \le c \le 10^5$$$) — пара городов, соединенных дорогой и длина этой дороги.
В последней строке входных данных находятся два целых числа $$$a$$$, $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$) — города, в которых находятся столицы первого и второго княжества.
Если разделить города между княжествами так, чтобы выполнялись все условия, невозможно, выведите число $$$-1$$$;
Иначе на одной строке выведите ровно $$$n$$$ чисел, где $$$i$$$-е число ($$$1 \le i \le n$$$) будет равно:
- $$$1$$$, если город с номером $$$i$$$ будет принадлежать $$$1$$$-му княжеству;
- $$$2$$$, если город с номером $$$i$$$ будет принадлежать $$$2$$$-му княжеству;
- $$$0$$$, если город с номером $$$i$$$ будет находиться на границе.
7 91 7 21 3 31 5 41 2 34 2 26 2 53 7 13 5 63 4 22 3
0 1 2 0 2 1 2
3 31 2 11 3 12 3 21 3
-1
5 42 4 12 1 15 3 34 3 11 4
1 0 2 2 2
Первый тест разобран в условии задачи.
Во втором тесте нельзя построить границу между княжествами, так как нет непустого множества городов, имеющих одинаковые расстояния до $$$a$$$ и $$$b$$$.
