TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

16.7% (7/42)

Description

Gremlins最近在農場上氾濫,它們經常會阻止牛們從農莊(牛棚_1)走到別的牛棚(牛_i的目的
地是牛棚_i).每一個gremlin只認識牛_i並且知道牛_i一般走到牛棚_i的最短路經.所以它
們在牛_i到牛棚_i之前的最後一條牛路上等牛_i. 當然,牛不願意遇到Gremlins,所以準備找
一條稍微不同的路經從牛棚_1走到牛棚_i.所以,請你為每一頭牛_i找出避免gremlin_i的最
短路經的長度.

和以往一樣, 農場上的M (2 <= M <= 200,000)條雙向牛路編號為1..M並且能讓所有牛到
達它們的目的地, N(3 <= N <= 100,000)個編號為1..N的牛棚.牛路i連接牛棚a_i
(1 <= a_i <= N)和b_i (1 <= b_i <= N)並且需要時間t_i (1 <= t_i <= 1,000)通過.
沒有兩條牛路連接同樣的牛棚,所有牛路滿足a_i!=b_i.在所有數據中,牛_i使用的牛棚_1到牛
棚_i的最短路經是唯一的.


以下是一個牛棚,牛路和時間的例子:

   1--[2]--2-------+
   ∣       |       |
  [2]     [1]     [3]
   |       |       |
   +-------3--[4]--4

  行程    最佳路徑  最佳時間  最後牛路
  p_1到p_2   1→2     2     1→2
  p_1到p_3   1→3     2     1→3
  p_1到p_4   1→2→4     5     2→4

當gremlins進入農場後:

  行程    最佳路徑  最佳時間   最後牛路
  p_1到p_2   1→3→2   3     1→2
  p_1到p_3   1→2→3   3     1→3
  p_1到p_4   1→3→4   6     2→4

Input Format

  • 第一行: 兩個空格分開的數, N和M

  • 第2..M+1行: 三個空格分開的數a_i, b_i,和t_i

Output Format

  • 第1..N-1行: 第i行包含一個數:從牛棚_1到牛棚_i+1並且避免從牛棚1到牛棚i+1最

短路經上最後一條牛路的最少的時間.如果這樣的路經不存在,輸出-1.

Sample Input

4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3

Sample Output

3
3
6

Hints

Problem Source

原TIOJ1689 / Elite USACO JAN 09

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 4000 65536 262144 1
1 4000 65536 262144 2
2 4000 65536 262144 3
3 4000 65536 262144 4
4 4000 65536 262144 5
5 4000 65536 262144 6
6 4000 65536 262144 7
7 4000 65536 262144 8
8 4000 65536 262144 9
9 4000 65536 262144 10