问题描述

给定一个 $n$ 个顶点，$m$ 条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从 $1$ 号点到其他点的最短路（顶点从 $1$ 到 $n$ 编号）。

输入格式

第一行两个整数 $n,m$ 。 接下来的 $m$ 行，每行有三个整数 $u, v, l$ ，表示 $u$ 到 $v$ 有一条长度为 $l$ 的边。 数据范围 对于 $10\%$ 的数据，$n = 2$，$m = 2$。 对于 $30\%$ 的数据，$n \le 5$，$m \le 10$。 对于 $100\%$ 的数据，$1 \le n \le 20000$，$1 \le m \le 200000$，$-10000 \le l \le 10000$，保证从任意顶点都能到达其他所有顶点。

输出格式

共 $n-1$ 行，第 $i$ 行表示 $1$ 号点到 $i+1$ 号点的最短路。

样例

输入

3 3
1 2 -1
2 3 -1
3 1 2

输出

-1
-2