CF1346D.Constructing the Dungeon

题目翻译

题目大意

Polycarp 正在制作主角可以探索的地牢。

该地牢由 $n$ 个房间组成，由 $m$ 条双向隧道连接，可以通过隧道从其他房间到达每个房间。

房间内有怪物守卫（第 $i$ 个房间内的怪物数量为 $a_i$），隧道内有金币（第 $i$ 条隧道内的金币数量为 $w_i$）。第 $i$ 条双向隧道连接着 $v_i$ 和 $u_i$ 两个房间。

Polycarp 已经确定了每条隧道中硬币的数量（$w_i$ 的值已经已知），现在他试图在房间中放置怪物（$a_i$ 的值还未知）。

Polycarp 希望以满足以下两个条件的方式来选择每个房间中怪物的数量：

1. 连接 $x$ 和 $y$ 房间的隧道的硬币数量应等于 $a_x$ 和 $a_y$ 的最小值。也就是说，$w_i=\min(a_{v_i},a_{u_i})$。

2. 地牢中的怪物数量越少越好。也就是说， $\sum_{i=1}^n a_i$ 的值是可能的最小值。

帮助 Polycarp 选择 $a_1,a_2,\cdots,a_n$，或者告诉他这是不可能的，他必须改变他的地牢计划。

第一行包含一个正整数 $t$（$1\le t\le100000$），表示测试用例数，然后是测试用例。

每个测试用例的第一行包含两个正整数 $n$ 和 $m$（$2\le n\le200000,n−1\le m\le \min(200000,\dfrac{n(n−1)}2)$），分别表示地宫中房间和隧道的数量。

接下来的 $m$ 行，每行描述地宫中的一条隧道。第 $i$ 行包含三个整数 $v_i,u_i,w_i$（$1\le v_i\le n,1\le u_i\le n,v_i\ne u_i, 1\le w_i\le10^9$），表示连接房间 $v_i$
和 $u_i$ 的双向隧道包含 $w_i$ 枚硬币。在每个测试用例中，隧道系统都是相连的（通过隧道可以从其他房间到达每个房间）。每对房间最多由一条隧道相连。

所有测试案例中 $n$ 的总和不超过 $200000$。同样，所有测试案例中 $m$ 的总和也不超过 $200000$。

对于每个测试用例，打印答案如下：

如果无法找到满足所有约束条件的 $a_1,a_2,\cdots,a_n$ 值，则在单独一行中输出 NO。

否则，第一行输出 YES，第二行输出 $n$ 个整数 $a_1,a_2,\cdots,a_n$。如果有多个有效答案，则输出其中任何一个。