#include <iostream>
#include <vector>

#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;
    }

    int elegirMenor(const vector <int> &dist, const vector <bool> &usado)
    {
        int minDist = INF;
        int nodoMin;
        for(int i=0; i<dist.size(); i++)
        {
            if(dist[i] < minDist && usado[i] == false)
            {
                minDist = dist[i];
                nodoMin = i;
            }
        }

        return nodoMin;
    }

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

        dist[inicio] = 0;

        for(int i=0; i<nodos; i++)
        {
            int n = elegirMenor(dist, usado);
            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;
                }
            }
        }

        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;
}