#include <iostream>
#include <vector>
#include <queue> ///priority_queue

#define INF (1 << 29) ///2^29 * 1 left shift

using namespace std;

struct Arista ///unidireccional
{
    int nodo;
    int costo;
};

Arista armar(int hasta, int costo)
{
    Arista ar;
    ar.nodo = hasta;
    ar.costo = costo;
    return ar;
}

struct Grafo
{
    vector <vector <Arista> > adj;
    int nodos, aristas, inicio;

    void leer()
    {
        cin >> nodos >> aristas;

        adj.resize(nodos+1);

        int desde, hasta, costo;

        for(int i=0; i<aristas; i++)
        {
            cin >> desde >> hasta >> costo;
            adj[desde].push_back(armar(hasta, costo));
            adj[hasta].push_back(armar(desde, costo));
        }

        cin >> inicio;
    }

    void Dijkstra()
    {
        vector <int> dist(nodos+1, INF);
        vector <bool> usado(nodos+1, false);

        priority_queue <pair<int, int>, vector <pair<int, int>>, greater<pair<int, int>> > pq;

        /**
        Metes elementos y siempre sacas el mayor
        Complejidad computacional = O(log(N))
        **/

        dist[inicio] = 0;
        pq.push({0, inicio});

        for(int i=0; i<nodos; i++)
        {
            pair<int, int> par = pq.top(); /// O(1)
            pq.pop();

            int n = par.second;
            usado[n] = true;

            for(int j=0; j<adj[n].size(); j++)
            {
                int vecino = adj[n][j].nodo;
                int costo = adj[n][j].costo;
                if(dist[n] + costo < dist[vecino])
                {
                    dist[vecino] = dist[n] + costo;
                    pq.push({dist[vecino], vecino}); ///E veces, log(n) -> O(E*log(N))
                    ///E -> arista
                    ///E -> N*(N-1)/2 -> cuadrático -> N*N
                    ///O(N*N*log(N)) -> O(N^2*log(N))
                }
            }
        }

        cout << "Distancias desde el inicio hasta cada nodo: " << endl;

        for(int i=1; i<dist.size(); i++)
        {
            cout << dist[i] << ", ";
        }
        cout << endl;

    }

};

int main()
{
    Grafo g;
    g.leer();
    g.Dijkstra();

    return 0;
}