#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#define infinit 2000000000

using namespace std;


struct muchie
{
    int x,y,cost;
    friend bool operator<(muchie a, muchie b)
{// la set (<) si priority_queue (>) semnele sunt opuse - nu uita sa schimbi cand rulezi codul
    return a.cost < b.cost;
}
};

struct nod
{
    int et,dist;
    friend bool operator<(nod a, nod b)
    {
    return a.dist < b.dist;
    }
};

int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int n,m,k;

    fin>>n>>m;


// Dijkstra


    int a,b,costul;
    int d[n+1],tata[n+1];
    multiset <nod> nS;
    vector <nod> la[n+1];
    nod nou;

    for(int i=1;i<=n;i++)
        {
            d[i]=infinit;
            tata[i]=0;
        }



    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>costul;
        cout<<a<<" "<<b<<" "<<costul<<"\n";
        nou.et=b;
        nou.dist=costul;
        la[a].push_back(nou);
    }

    int start;
    cin>>start;
    nou.et=start;
    nou.dist=0;
    nS.insert(nou);
    d[start]=0;




    while(!nS.empty())
    {
        nod minim=*(nS.begin());
      
        nS.erase(nS.begin());
        for(int i=0;i<la[minim.et].size();i++)
        {
          
            nod adiacent=la[minim.et][i];
            if(d[adiacent.et]>d[minim.et]+adiacent.dist)
                {
                    if(d[adiacent.et]!=infinit)
                        nS.erase(nS.find(adiacent));

                    d[adiacent.et]=d[minim.et]+adiacent.dist;
                   
                  
                    nS.insert(adiacent);
                }
           
        }
      
    }

    for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";

  



    return 0;
}