#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; const int MAXN = 1505; const int INF = INT_MAX / 2; vector<vector<int>> graph(MAXN, vector<int>(MAXN, INF)); vector<int> dist(MAXN, INF); vector<bool> visited(MAXN, false); void dijkstra(int n) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; dist[1] = 0; pq.push({0, 1}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (visited[u]) continue; visited[u] = true; for (int v = 1; v <= n; ++v) { if (graph[u][v] != INF && dist[v] > dist[u] + graph[u][v]) { dist[v] = dist[u] + graph[u][v]; pq.push({dist[v], v}); } } } } int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { cin >> graph[i][j]; if (graph[i][j] == -1) { graph[i][j] = INF; } } } dijkstra(n); for (int i = 1; i <= n; ++i) { cout << dist[i] << endl; } return 0; }