<jupyter_start><jupyter_text>013AGC 王国には N 個の交差点があり、それぞれ 1, 2, 3, ..., N と番号付けられています。また M 本の道路があり、道路 i は交差点 A[i] と交差点 B[i] を双方向に結び、交差点間の移動にかかる時間は C[i] 秒です。今日から数えて i (1≦i≦N) 日目には交差点 i でイベントが開催されるため、移動の際には交差点 i を経由しなければなりません、i = 1, 2, 3, ..., N それぞれについて、i 日目に交差点 1 から交差点 N まで移動するのにかかる時間の最小値を求めてください。【制約】・2 ≦ N ≦ 100000・1 ≦ A[i] < B[i] ≦ N・(A[i], B[i]) ≠ (A[j], B[j]) [i ≠ j]・1 ≦ C[i] ≦ 10000・いくつかの道路を通って、都市 1 から都市 N までたどり着ける・入力はすべて整数 入力形式N MA[1] B[1] C[1]A[2] B[2] C[2] : A[M] B[M] C[M]<jupyter_code># 入力例 1
7 9
1 2 2
1 3 3
2 5 2
3 4 1
3 5 4
4 7 5
5 6 1
5 7 6
6 7 3

# 出力例 1
8
8
9
9
8
8
8
# 入力例 2
4 3
1 2 1
2 3 10
3 4 100

# 出力例 2
111
111
111
111
# 入力例 3
4 3
1 2 314
1 3 159
1 4 265

# 出力例 3
265
893
583
265
# 入力例 4
31
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31

# 出力例 4
9<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12184412733260154, 'fraction_numerical': 0.2502744237102086, 'mean_word_length': 2.880851063829787, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '363818', 'license': 'Apache-2.0', 'n_tokens_mistral': 850, 'n_tokens_neox': 680, 'n_words': 213, 'path': '.ipynb_checkpoints/013_problem-checkpoint.ipynb', 'repo_name': 'SeongHaedu/Competitive-programming', 'size': '911'}