통행 차단

농부 존의 농장에는 목초지가 $N$개 있고($2 \leq N \leq 50{,}000$), 길이가 1인 양방향 길 $N-1$개가 목초지를 잇는다. 이 길만 따라가도 어느 목초지에서 어느 목초지로든 갈 수 있다.

농장은 연결되어 있지만, 존은 길 하나가 막히는 상황을 걱정한다. 길 하나가 막히면 농장은 목초지 두 무리로 갈라지고, 소는 같은 무리 안에서만 오갈 수 있다. 그래서 존은 양방향 길 $M$개를 더 놓는다($1 \leq M \leq 50{,}000$). 새로 놓은 길의 길이는 $10^9$ 이하의 양의 정수다. 소는 원래 있던 길 중 하나가 막히기 전까지는 원래 있던 길만 쓴다.

원래 있던 길 하나가 막히면 농장은 두 조각으로 갈라진다. 존은 새로 놓은 길 중 하나를 골라 두 조각을 다시 이어서, 소가 다시 어느 목초지에서 어느 목초지로든 갈 수 있게 한다.

원래 있던 길마다 그 길을 대신할 가장 짧은 길의 길이를 구하라.

첫째 줄에 $N$과 $M$이 주어진다. 다음 $N-1$개 줄에는 원래 있던 길이 정수 $p$, $q$로 주어진다. 두 목초지 $p$와 $q$를 잇는 길이고, $p \neq q$이며 두 값은 $1$ 이상 $N$ 이하다. 이어지는 $M$개 줄에는 새로 놓은 길이 정수 $p$, $q$, $r$로 주어진다. 목초지 $p$와 $q$를 잇고 길이가 $r$인 길이다. 두 목초지 사이에 놓인 길은 많아야 하나다.

$N-1$개 줄을 출력한다. $i$번째 줄에는 입력에서 $i$번째로 주어진 원래 길이 막혔을 때 농장을 다시 잇는 가장 짧은 새 길의 길이를 출력한다. 대신할 길이 없으면 -1을 출력한다.