Jeff Needs Help

Problem Statement:

It is 2090 and Blue Origin’s manned space shuttle beat SpaceX in the race to finding a habitable galaxy. However, the shuttle is running low on fuel. So, the captain, coincidentally named Jeff, has to find the shortest distance to between the shuttle and every other planet. This is what he knows: There are N planets. The shuttle is at Planet Green. There are M safe routes connecting the planets. The ith route goes from city X_i to city Y_i and has a length of Z_i. Jeff assigns you this task because you are the smartest in the room. He wants a clear symbol, -1 if it is impossible to go to any particular city.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ min(N × (N - 1) / 2, 10⁵)
• 1 ≤ ≤ X_i, Y_i ≤ N (1 ≤ i ≤ M)
• 1 ≤ Z_i ≤ 10⁹ (1 ≤ i ≤ M)
• (X_i, Y_i) ≠ (X_j, Y_j) (i ≠ j, 1 ≤ i, j ≤ M)

Subtask 1: 10 points

• Z_i = 1 (1 ≤ i ≤ N)

Subtask 2: 20 points

• M = N - 1

Subtask 3: 20 points

• 1 ≤ N ≤ 100

Subtask 4: 30 points

• 1 ≤ N ≤ 1000

Subtask 5: 20 points

• No additional constraints

Input Format:

• The first line contains two integers N and M
• The next M lines contain three integers, X_i, Y_i and Z_i

Output Format:

• Print a single line containing N - 1 integers where the ith integer represents the shortest distance from the capital city to the i + 1th city

Sample input:

3 3 1 2 3 2 3 1 3 1 1 

Sample output:

2 1