K. Дерево кратчайших путей

Дан неориентированный взвешенный граф. Для каждой вершины выведите её родителя в дереве кратчайших путей из вершины 1 — то есть вершину, из которой в неё выгоднее всего прийти.

Родителем вершины $v$ считается наименьшая вершина $u$, для которой

У вершины 1 и у недостижимых вершин родителя нет — для них выведите $0$.

Первая строка содержит числа $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$ чисел — родители вершин.