Вам дан неориентированный граф из $$$n$$$ вершин и $$$m$$$ рёбер. Найдите кратчайший путь от вершины $$$1$$$ до всех остальных вершин с помощью алгоритма Де́йкстры («Dikjstra's algorithm»).
В первой строке содержатся два целых числа $$$n$$$ и $$$m$$$ $$$(2 \leq n \leq 100, 0 \leq m \leq \frac{n(n-1)}{2})$$$.
В следующих $$$m$$$ строках содержатся по $$$3$$$ целых числа: $$$u$$$, $$$v$$$ и $$$w$$$, обозначающие неориентированное ребро между вершинами $$$u$$$ и $$$v$$$ весом $$$w$$$ $$$(1 \leq u, v \leq n, 0 \leq w \leq 10^5)$$$.
Выведите кратчайший путь от вершины $$$1$$$ до каждой вершины $$$2, \dots, n$$$. Если вершина недостижима из вершины $$$1$$$, выведите $$$-1$$$.
2 11 2 1
1
5 51 2 71 3 41 4 92 3 63 4 2
7 4 6 -1
5 61 5 22 1 63 4 24 2 95 3 72 3 4
6 9 12 2
| April Fools Day Contest 2026 |
|---|
| Закончено |
