给你一个 $n$ 个点的图，初始时只有一条 $1\rightarrow n$ 的边权为 $k$ 的边。

有 $m$ 次操作，每次操作会增加一条 $u\rightarrow v$ 的边，每次增加边过后你需要立即输出 $1\rightarrow n$ 的最短路。

$1\le n, m\le 5\times 10^5$