D. Построение подземелья
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп разрабатывает RPG-видеоигру, главный герой которой сражается с монстрами и ищет сокровища в подземельях. Сейчас Поликарп добавляет в игру одно из подземелий.

Подземелье состоит из $$$n$$$ комнат, соединенных $$$m$$$ двусторонними туннелями, используя которые, можно добраться из любой комнаты в любую другую комнату. Комнаты охраняются монстрами (количество монстров в $$$i$$$-й комнате равно $$$a_i$$$), а в туннелях можно найти золотые монеты (количество монет в $$$i$$$-м туннеле равно $$$w_i$$$). $$$i$$$-й двусторонний туннель соединяет комнаты $$$v_i$$$ и $$$u_i$$$.

Поликарп уже определил количество монет в каждом туннеле (значения $$$w_i$$$ уже известны), и теперь он пытается распределить монстров по комнатам (значения $$$a_i$$$ пока не известны). Поликарп хочет выбрать количество монстров в каждой комнате так, чтобы выполнялись два условия:

  • количество монет в туннеле, соединяющем комнаты $$$x$$$ и $$$y$$$, равно минимум из $$$a_x$$$ и $$$a_y$$$. То есть, для каждого туннеля $$$i$$$ выполняется $$$w_i = \min (a_{v_i}, a_{u_i})$$$;
  • суммарное количество монстров во всех комнатах как можно меньше. То есть, значение $$$a_1 + a_2 + \dots + a_n$$$ — минимально возможное.

Помогите Поликарпу выбрать значения $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$, или скажите ему, что это невозможно и в плане подземелья что-то необходимо поменять.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 100000$$$) — количество наборов входных данных. Затем следуют сами наборы входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 200000$$$; $$$n - 1 \le m \le \min(200000, \frac{n(n-1)}{2})$$$) — количество комнат и туннелей в подземелье, соответственно.

Затем следуют $$$m$$$ строк, каждая из которых содержит описание туннеля. В $$$i$$$-й строке заданы три целых числа $$$v_i$$$, $$$u_i$$$ и $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$v_i \ne u_i$$$; $$$1 \le w_i \le 10^9$$$), обозначающих двусторониий туннель между комнатами $$$v_i$$$ и $$$u_i$$$, содержащий $$$w_i$$$ монет. В каждом наборе входных данных система туннелей связна (можно добраться из любой комнаты в любую другую по туннелям). Каждая пара комнат соединена не более чем одним туннелем.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200000$$$. Аналогично, сумма $$$m$$$ по всем наборам входных данных не превосходит $$$200000$$$.

Выходные данные

Выведите ответ на каждый набор входных данных следующим образом:

Если невозможно найти значения $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$, удовлетворяющие всем условиям, в единственной строке выведите NO. Иначе выведите YES в первой строке и $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ во второй строке. Если возможных ответов несколько, выведите любой из них.

Пример
Входные данные
3
3 2
1 2 1
2 3 1
5 7
3 2 7
3 4 9
1 5 5
1 2 5
4 1 5
4 2 7
3 1 5
4 4
1 2 5
3 2 2
4 1 3
3 4 4
Выходные данные
YES
1 1 1
YES
5 7 9 9 5
NO