Ford-Bellman

#define _CRT_SECURE_NO_WARNINS
#include <fstream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

//bool dfs(int v, int prev){
//  used[v] = 1;
//  for (int i = 0; i < mat[v].size(); i++)
//  {
//
//      if (used[mat[v][i]] == 0){
//          dfs(mat[v][i], v);
//          used[v] = 2;
//      }
//  }
//  used[v] = 2;
//  return true;
//}
//
//bool cheker(vector<int> ch, int f){
//  for (int i = f; i < ch.size(); i++){
//      if (ch[i] != 2){
//          return false;
//      }
//
//  }return true;
//}

struct edges{
    int x, y, value;
};


int main(){



    ifstream fin("input.txt");
    ofstream fout("output.txt");


    int n, m, s;

    fin >> n >> m >> s;
    s--;
    vector<edges> edge(m);
    vector <int> d(n, INT_MAX);


    for (int i = 0; i < m; i++){
        int a, b, c;
        fin >> a >> b >> c;
        a--;
        b--;
        edge[i].x = a;
        edge[i].y = b;
        edge[i].value = c;
    }
    d[s] = 0;
    bool change = true;
    while (change){
        change = false;
        for (int i = 0; i < m; i++) {
            if (d[edge[i].x] < INT_MAX) {//d[0]
                if ((d[edge[i].y] > (d[edge[i].x] + edge[i].value))){
                    d[edge[i].y] = (d[edge[i].x] + edge[i].value);
                    change = true;
                }
            }
        }
    }

    for (int i = 0; i < n; i++){
        if (d[i] != INT_MAX && i != n - 1){
            fout << d[i] << ' ';
        }
        else if (i == n - 1 && d[i] != INT_MAX){
            fout << d[i];
        }
    }

}