#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector< vector<pair<int,int> > > graph;
vector<int> visited;
vector<int> dist;
void Dijkstra(int source,int n)//n is the no. of vertices;
{
for(int i=1;i<=n;i++)// Initially setting shortest distance of each vertex from the source vertex to be infinity
dist[i]=INT_MAX;
dist[source]=0;
priority_queue<pair<int,int>, vector<pair<int,int> >,std::greater<pair<int,int> > >p;
p.push(make_pair(0,source));
while(p.empty()==false)
{
pair<int,int> current = p.top();
p.pop();
int cv=current.second;//current vertex which has been extracted out from min heap
int cw=current.first;//current min dist till this vertex from the source
if(visited[cv]==1)//if the node is already visited then continue;
continue;
visited[cv]=1;//mark the node as visited
for(vector<pair<int,int> >::iterator itr=graph[cv].begin();itr!=graph[cv].end();itr++)
{
if(visited[itr->second]==0&&dist[itr->second]>cw+itr->first)
{ dist[itr->second]=cw+itr->first;
p.push(make_pair(dist[itr->second],itr->second));
}
}
}
}
int main()
{
int n,m,w;
cin>>n>>m;
graph = vector <vector<pair<int, int> > > (n+1);
visited = vector<int> (n+1,0);
dist=vector<int> (n+1);
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v>>w;
graph[u].push_back(make_pair(w,v));
graph[v].push_back(make_pair(w,u));
}
int source;
cin>>source;
Dijkstra(source,n);
for(int i=1;i<=n;i++)
cout<<dist[i]<<" ";
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZlY3RvcjwgdmVjdG9yPHBhaXI8aW50LGludD4gPiA+IGdyYXBoOwp2ZWN0b3I8aW50PiB2aXNpdGVkOwp2ZWN0b3I8aW50PiBkaXN0OwoKdm9pZCBEaWprc3RyYShpbnQgc291cmNlLGludCBuKS8vbiBpcyB0aGUgbm8uIG9mIHZlcnRpY2VzOwp7CiAgICBmb3IoaW50IGk9MTtpPD1uO2krKykvLyBJbml0aWFsbHkgc2V0dGluZyBzaG9ydGVzdCBkaXN0YW5jZSBvZiBlYWNoIHZlcnRleCBmcm9tIHRoZSBzb3VyY2UgdmVydGV4IHRvIGJlIGluZmluaXR5CiAgICAgICAgZGlzdFtpXT1JTlRfTUFYOwoKICAgIGRpc3Rbc291cmNlXT0wOwoKICAgIHByaW9yaXR5X3F1ZXVlPHBhaXI8aW50LGludD4sIHZlY3RvcjxwYWlyPGludCxpbnQ+ID4sc3RkOjpncmVhdGVyPHBhaXI8aW50LGludD4gPiA+cDsKICAgIHAucHVzaChtYWtlX3BhaXIoMCxzb3VyY2UpKTsKCiAgICB3aGlsZShwLmVtcHR5KCk9PWZhbHNlKQogICAgewogICAgICAgIHBhaXI8aW50LGludD4gY3VycmVudCA9IHAudG9wKCk7CiAgICAgICAgcC5wb3AoKTsKICAgICAgICBpbnQgY3Y9Y3VycmVudC5zZWNvbmQ7Ly9jdXJyZW50IHZlcnRleCB3aGljaCBoYXMgYmVlbiBleHRyYWN0ZWQgb3V0IGZyb20gbWluIGhlYXAKICAgICAgICBpbnQgY3c9Y3VycmVudC5maXJzdDsvL2N1cnJlbnQgbWluIGRpc3QgdGlsbCB0aGlzIHZlcnRleCBmcm9tIHRoZSBzb3VyY2UKCiAgICAgICAgaWYodmlzaXRlZFtjdl09PTEpLy9pZiB0aGUgbm9kZSBpcyBhbHJlYWR5IHZpc2l0ZWQgdGhlbiBjb250aW51ZTsKICAgICAgICAgICAgY29udGludWU7CgogICAgICAgIHZpc2l0ZWRbY3ZdPTE7Ly9tYXJrIHRoZSBub2RlIGFzIHZpc2l0ZWQKCiAgICAgICAgZm9yKHZlY3RvcjxwYWlyPGludCxpbnQ+ID46Oml0ZXJhdG9yIGl0cj1ncmFwaFtjdl0uYmVnaW4oKTtpdHIhPWdyYXBoW2N2XS5lbmQoKTtpdHIrKykKICAgICAgICB7CiAgICAgICAgICAgICBpZih2aXNpdGVkW2l0ci0+c2Vjb25kXT09MCYmZGlzdFtpdHItPnNlY29uZF0+Y3craXRyLT5maXJzdCkKICAgICAgICAgICAgIHsgZGlzdFtpdHItPnNlY29uZF09Y3craXRyLT5maXJzdDsKICAgICAgICAgICAgIHAucHVzaChtYWtlX3BhaXIoZGlzdFtpdHItPnNlY29uZF0saXRyLT5zZWNvbmQpKTsKCiAgICAgICAgICAgICB9CgogICAgICAgIH0KCiAgICB9CgoKCn0KCmludCBtYWluKCkKewogICAgaW50IG4sbSx3OwogICAgY2luPj5uPj5tOwoKICBncmFwaCA9IHZlY3RvciA8dmVjdG9yPHBhaXI8aW50LCBpbnQ+ID4gPiAobisxKTsKICB2aXNpdGVkID0gdmVjdG9yPGludD4gKG4rMSwwKTsKICBkaXN0PXZlY3RvcjxpbnQ+IChuKzEpOwoKICBmb3IoaW50IGk9MTtpPD1tO2krKykKICB7CiAgICAgIGludCB1LHY7CiAgICAgIGNpbj4+dT4+dj4+dzsKICAgICAgZ3JhcGhbdV0ucHVzaF9iYWNrKG1ha2VfcGFpcih3LHYpKTsKICAgICAgZ3JhcGhbdl0ucHVzaF9iYWNrKG1ha2VfcGFpcih3LHUpKTsKICB9CiAgaW50IHNvdXJjZTsKICBjaW4+PnNvdXJjZTsKCiAgRGlqa3N0cmEoc291cmNlLG4pOwoKICBmb3IoaW50IGk9MTtpPD1uO2krKykKICAgIGNvdXQ8PGRpc3RbaV08PCIgIjsKCgogICAgcmV0dXJuIDA7Cn0K