Magical Resistance

You are given a network of caves numbered from 1 to \(N\). There are \(M\) bidirectional connections between them, and each connection is associated with a magical resistance cost. The task is to compute the minimum cumulative magical resistance required to travel from cave 1 to every other cave using these connections. If a cave is unreachable, output \(-1\) for that cave.

You can model this problem using Dijkstra's algorithm. For a connection between cave \(u\) and cave \(v\) with cost \(w\), the formula for relaxing the distance is:

\(d[v] = \min(d[v], d[u] + w)\)

Input Format: The first line contains two integers, \(N\) and \(M\). Each of the next \(M\) lines contains three integers \(u, v, w\), representing a bidirectional connection between cave \(u\) and cave \(v\) with magical resistance \(w\).

Output Format: Output a single line with \(N\) space-separated integers representing the minimum magical resistance from cave 1 to cave \(i\) for \(1 \leq i \leq N\). For unreachable caves, output \(-1\). The resistance to cave 1 is always \(0\).

inputFormat

The first line contains two integers: \(N\) (the number of caves) and \(M\) (the number of connections). The following \(M\) lines each contain three integers \(u\), \(v\), and \(w\), representing a bidirectional connection between cave \(u\) and cave \(v\) with resistance \(w\).

outputFormat

Output a single line containing \(N\) space-separated integers. The \(i^{th}\) integer denotes the minimum magical resistance required to reach cave \(i\) from cave 1. If cave \(i\) is unreachable, print \(-1\) for that cave.

## sample

5 6
1 2 2
1 3 4
2 3 1
3 4 2
2 5 7
4 5 3

0 2 3 5 8

</p>