K. Глубина в дереве кратчайших путей

Как классная задача K, но выведите не родителей, а глубину каждой вершины в дереве кратчайших путей — количество рёбер от вершины 1 до неё по этому дереву.

Родитель определяется тем же правилом: наименьшая вершина $u$ с $\mathrm{dist}[u] + w(u, v) = \mathrm{dist}[v]$. Глубина вершины 1 равна нулю; для недостижимых выведите $-1$.

Считать глубины удобно, перебирая вершины в порядке возрастания расстояния: к моменту, когда очередь доходит до $v$, глубина её родителя уже посчитана. Веса строго положительны, поэтому такой порядок законен.

Первая строка содержит числа $n$ ($1 \le n \le 10^5$) и $m$ ($0 \le m \le 2 \cdot 10^5$).

Далее идут $m$ строк с рёбрами: концы и вес $w$ ($1 \le w \le 10^4$).

Одна строка из $n$ чисел.