#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INFINIT = 1000000000;

int main() {
	int n, s;
	if (!(cin >> n >> s)) return 0;

	vector<vector<int>> a(n + 1, vector<int>(n + 1));
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			cin >> a[i][j];

	vector<int> d(n + 1, INFINIT), f(n + 1, 0);

	// nodul sursa este s
    #include <bits/stdc++.h>
    using namespace std;

    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int N, M;
        if (!(cin >> N >> M)) return 0;

        vector<vector<pair<int,int>>> adj(N + 1);
        for (int i = 0; i < M; ++i) {
            int A, B, C;
            cin >> A >> B >> C;
            adj[A].emplace_back(B, C);
        }

        const long long INF = (long long)4e18;
        vector<long long> dist(N + 1, INF);
        dist[1] = 0;

        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
        pq.emplace(0LL, 1);

        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d != dist[u]) continue;
            for (auto &e : adj[u]) {
                int v = e.first;
                long long w = e.second;
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.emplace(dist[v], v);
                }
            }
        }

        // Output distances for nodes 2..N. If unreachable output 0.
        for (int i = 2; i <= N; ++i) {
            if (dist[i] == INF) cout << 0;
            else cout << dist[i];
            if (i < N) cout << ' ';
        }
        cout << '\n';
        return 0;
    }

	f[s] = 1;
	d[s] = 0;
    for (int i = 1; i <= n; ++i) { d[i] = INFINIT; f[i] = 0; }
    d[s] = 0;

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.emplace(0, s);

    while (!pq.empty()) {
        auto [dist, u] = pq.top(); pq.pop();
        if (dist != d[u]) continue; 
        if (f[u]) continue;
        f[u] = 1;

        for (int v = 1; v <= n; ++v) {
            if (f[v] == 0 && d[v] > d[u] + a[u][v]) {
                d[v] = d[u] + a[u][v];
                pq.emplace(d[v], v);
            }
        }
    }

    for (int i = 1; i <= n; ++i)
        f[i] = 1;

	for (int k = 1; k < n; ++k) {
		int pmax = 0;
		for (int i = 1; i <= n; ++i)
			if (f[i] == 0 && d[i] < d[pmax])
				pmax = i;

		if (pmax != 0 && d[pmax] < INFINIT) {
			f[pmax] = 1;
			for (int i = 1; i <= n; ++i)
				if (f[i] == 0 && d[i] > d[pmax] + a[pmax][i])
					d[i] = d[pmax] + a[pmax][i];
		} else {
			break;
		}
	}

	// afisare 
	for (int i = 1; i <= n; ++i) {
		if (d[i] >= INFINIT) cout << "INF";
		else cout << d[i];
		if (i < n) cout << ' ';
	}
	cout << '\n';

	return 0;
}