//#include <iostream>
#include <vector>
#include <iostream>
#include <fstream>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;
/*
struct node{
    void* el[2] = {nullptr, nullptr};
    int value = 0;
};

bool operator<(const node& a, const node& b){
    return a.value > b.value;
};


//format:
// n - number of nodes
// n1,n2,n3,... the parent of each node
// e scris oribil de complicat pt ca asa imi place mie sa ma auto-torturez
vector<int> pruferEncode(bool print=false) {
    int n;

    ifstream in("tree.txt");
    in >> n;

    vector<int> pruf;
    int currentNodes = n;
    vector<int> nodes(n);
    vector<int> degrees(n, 0);

    in >>nodes[0];
    for (int i = 1; i < n; i++) {
        in >> nodes[i];
        degrees[nodes[i]]++;
    }
    int minNode;
    while (currentNodes > 1) {
        [&](int &minNode) {
            for (int i = 0; i < n; i++) {
                if (nodes[i] != -1 && degrees[i] == 0) {
                    minNode = i;
                    degrees[nodes[i]]--;
                    if(print)
                        cout << nodes[minNode]<<' ';
                    pruf.push_back(nodes[minNode]);
                    nodes[i] = -1;
                    currentNodes--;
                    return;
                }
            }
            minNode = 1;
        }(minNode);
    }
    cout<<'\n';
    return pruf;
}


vector<int> pruferDecode(vector<int> coded,bool print=false){



    auto smallestNonAppearing = [&](){
        int j;
        for(int i = 0; i <= coded.size(); i++){
            for(j = 0; j < coded.size(); j++){
                if(coded[j] == i)
                    break;
            }
            if(j == coded.size())
                return i;
        }
        return -1;
    };

    vector<pair<int,int>> parinteCopil;

    for(int i = 0; i < coded.size();i++){
        int mn = smallestNonAppearing();
        parinteCopil.emplace_back(coded[i], mn);
        coded[i] = mn;
        //coded.push_back(mn);
    }
    vector<int> tree(coded.size()+1, -1);

    for(auto p: parinteCopil){
        tree[p.second] = p.first;
    }

    if(print)
        for(auto p: tree){
            cout<<p<<' ';
        }
    cout<<'\n';
    return tree;
}


map <char, string> hufdict;

void extracthuf(node* root, string now){
    cout<<root->el[0]<<' ';
    if(root->el[1] == nullptr) {
        char c = *((char *) root->el[0]);
        hufdict[*((char *) root->el[0])] = now;
    }
    else{
        string s1 = now , s2 = now;
        s1 += "0";
        s2 += "1";
        extracthuf((node*)root->el[0], s1);
        extracthuf((node*)root->el[1], s2);
    }
}


void encodeHuf(string s){

   map<char, int> freq;

   for(char c : s){
       if(freq.find(c) == freq.end())
           freq[c] = 0;
       freq[c]++;
   }

   //sorted by node.value
   priority_queue<node> pq;

    for(auto p : freq){
        node n;
        n.value = p.second;
        n.el[0] = new char;
        n.el[1] = nullptr;
        *((char*)n.el[0]) = 1;
        pq.push(n);
        cout<<p.second<<' ';
    }
    cout<<'\n';
    node *n1, *n2, *n3;
    //cout<<pq.size();
    while(pq.size() > 2 ){

        n1 = new node;
        n2 = new node;
        n3 = new node;
        node m = pq.top();
        *n1 = m;
        pq.pop();
        *n2 = pq.top();
        pq.pop();
        n3->el[0] = n1;
        n3->el[1] = n2;
        n3->value = n1->value+n2->value;
        pq.push(*n3);
    }
    node root;
    *n1 = pq.top();
    pq.pop();
    *n2 = pq.top();
    pq.pop();
    root.el[0] = n1;
    root.el[1] = n2;
    root.value = n1->value + n2->value;
    //cout<<root.el[0];

    node* n4 = &root;
    node* n5 = (node*)root.el[1];


    string sr = "";
    extracthuf(&root, sr);




}


bool wasVisited(int node, vector<int> visited);

void dijkstra(){

    ifstream in("graf");

    int start, nodesC;
    in>>nodesC>>start;
    int node1, node2, cost;
    vector< vector< pair<int, int> > > nodes(nodesC+1); //nod cost
    vector<int> costs(nodesC+1, INT_MAX);
    vector<int> visited;
    while(in>>node1>>node2>>cost){
        nodes[node1].push_back({node2, cost});
    }
    costs[start] = 0;

    queue<int> toScan;;
    toScan.push(start);

    while(!toScan.empty()){
        //updating costs
        int current = toScan.front();
        //int minNode;
        toScan.pop();
        visited.push_back(current);
        for(auto n: nodes[current]){

            if(costs[n.first] > costs[current] + n.second) {
                if(find(visited.begin(), visited.end(),n.first) == visited.end())
                    toScan.push(n.first);
                costs[n.first] = costs[current] + n.second;
            }
        }
    }

    for(int i = 1; i < costs.size(); i++){
        if(costs[i] == INT_MAX)
            cout<<-1<<' ';
        else
            cout<<costs[i]<<' ';
    }
}
*/
void bellmanFord(){

    ifstream in("bellmanford.in");

    int start, nodesC;
    in>>nodesC>>start;
    start = 1;
    int node1, node2, cost;
    vector< vector< pair<int, int> > > nodes(nodesC+1); //nod cost
    vector<int> costs(nodesC+1, INT_MAX);
    vector<int> visited;
    while(in>>node1>>node2>>cost){
        nodes[node1].push_back({node2, cost});
    }
    costs[start] = 0;

    bool update = true;
    for(int k = 0; k < nodes.size()-1;k++){
        update = false;
        for(int i = 1; i < nodes.size(); i++){
            for(auto a: nodes[i]){
                if(costs[i] != INT_MAX){
                    if(costs[a.first] > costs[i] + a.second) {
                        costs[a.first] = costs[i] + a.second;
                        update = true;
                    }
                }
            }
        }
    }
    ofstream out("bellmanford.out");
    for(int i = 1; i < nodes.size(); i++) {
        for (auto a: nodes[i]) {
            if (costs[i] != INT_MAX) {
                if (costs[a.first] > costs[i] + a.second) {
                    out << "Ciclu negativ!";
                    return;
                }
            }
        }
    }


    for(int i = 2; i < costs.size(); i++){
        if(costs[i] == INT_MAX)
            out<<-1<<' ';
        else
            out<<costs[i]<<' ';
    }

}



int main() {
    //pruferDecode(pruferEncode(false), false);

    //encodeHuf("abracadabrag");

    //dijkstra();
    bellmanFord();

    return 0;
}