問(wèn)題描述

給定一個(gè)n個(gè)頂點(diǎn)，m條邊的有向圖（其中某些邊權(quán)可能為負(fù)，但保證沒(méi)有負(fù)環(huán)）。請(qǐng)你計(jì)算從1號(hào)點(diǎn)到其他點(diǎn)的最短路（頂點(diǎn)從1到n編號(hào)）。

輸入格式

第一行兩個(gè)整數(shù)n, m。

接下來(lái)的m行，每行有三個(gè)整數(shù)u, v, l，表示u到v有一條長(zhǎng)度為l的邊。

輸出格式

共n-1行，第i行表示1號(hào)點(diǎn)到i+1號(hào)點(diǎn)的最短路。

樣例輸入

3 3

1 2 -1

2 3 -1

3 1 2

樣例輸出

-1

-2

數(shù)據(jù)規(guī)模與約定

對(duì)于10%的數(shù)據(jù)，n = 2，m = 2。

對(duì)于30%的數(shù)據(jù)，n <= 5，m <= 10。

對(duì)于100%的數(shù)據(jù)，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保證從任意頂點(diǎn)都能到達(dá)其他所有頂點(diǎn)。