Elo 在勤勤恳恳地经营她的大农田一段时间后有了一定积蓄，因此 Elo 决定扩充农田面积，同时需要雇佣更多的员工。扩充员工后，Elo 发现因为人数的增加，她不能像以前一样现场发放工资了，因此 Elo 决定使用银行转账的方式来发放工资。Elo 目前雇佣了$n$名员工，每名员工都有一个专门接收工资的银行卡，员工们之间或员工和 Elo 之间的转账需要的手续费并不完全相同。同时因为各种原因，Elo 只能直接转账给部分员工，剩下的员工需要通过员工间转账来间接发放工资。为了尽量减少在转账时的手续费开销，同时知晓有哪些员工不能通过转账发放工资，Elo 希望你能帮她计算她转账给每个员工时所需的最低开销。

第一行，包含两个正整数$n, m(1\leqslant n \leqslant 2\times 10 ^ 3, 1\leqslant m \leqslant 10 ^ 5)$，表示有$n$名员工，Elo的编号为$n + 1$，员工们之间或员工和 Elo 之间共有$m$对可以转账。
接下来有$m$行，对于第$i$行，包含三个整数$x, y, z(1 \leqslant x, y \leqslant n + 1, 0\leqslant z \leqslant 10 ^ 5)$，表示$x$号员工和$y$号员工（若为$n + 1$，则表示 Elo）之间转账需要$z$的手续费。
保证$x\ne y$，且不会有两个员工之间存在两种或以上的转账关系。

共$n$行，对于第$i$行，输出一个答案，表示 Elo 转账给$i$号员工最少需要多少手续费，若不能转账给该员工，则输出impossible。

对于样例一，Elo（编号为$3$）转账给$1$号员工可通过$2$号员工间接转账，需手续费$1 + 1 = 2$，对于$2$号员工可直接转账，需手续费$1$。

本题允许$O(n^2)$算法通过，但请尽量使用$O(m\log n)$级别的算法。