#591. 新年的密码锁

样例一

input

5 5
1 2
2 3
2 4
1 5
2 4 511332337
1 4 919238353
5 1 597538394
2 1 170644152
5 2 848575637



output

-1
-1
919238353
1089882505
1938458142



限制与约定

$1$ $16$ $16$
$2$ $300$ $13$
$3$ $3000$ $19$
$4$ $200000$ $x_i = y_i - 1$ $23$
$5$ $29$