#include <fstream>
#define INF 1000000000
#define NMAX 10000
#define InFile "dijkstra.in"
#define OutFile "dijkstra.out"

using namespace std;
struct Arc {int vf; int c;};

int n, x0;
Arc G[NMAX][NMAX];
int dmin[NMAX]; //distantele minime
int prec[NMAX]; //pot reconstitui drumul
int M[NMAX]; //multimea varfurilor selectate
int h[NMAX], lgh; //in h sunt varfurile organizate ca min-heap dupa dmin
int poz[NMAX]; //poz[i]=-1 daca vf i nu a fost pus in heap, respectiv pozitia nodului i in heap


void citire();
void dijkstra();
int ExtractMin();
void InsertHeap(int vf);
void Upgrade(int fiu);
void afisare();

int main()
{
citire();
dijkstra();
afisare();
return 0;
}


void adauga_arc(int x, int y, int c)
{
G[x][0].c++;
G[x][G[x][0].c].vf=y;
G[x][G[x][0].c].c=c;
}

void citire()
{
int i, m, x, y, c;	
ifstream fin(InFile);
fin>>n>>x0>>m;
for (i=0; i<m; i++)
    {fin>>x>>y>>c;
     adauga_arc(x,y,c);}
}

void dijkstra()
{
int i, nrs=1, j, vfmin;
for (i=1; i<=n; i++) {dmin[i]=INF; prec[i]=x0; poz[i]=-1;}
dmin[x0]=0; prec[x0]=-1; poz[x0]=1; h[1]=x0; lgh=1;
while (nrs<n) //nu au fost selectate toate varfurile
	{
	vfmin=ExtractMin();
	M[vfmin]=1; nrs++;
	for (j=1; j<=G[vfmin][0].c; j++)
			if (!M[G[vfmin][j].vf]) //nu a fost deja selectat
				if (dmin[G[vfmin][j].vf]>dmin[vfmin]+G[vfmin][j].c) //obtin ceva mai bun
					{
				    dmin[G[vfmin][j].vf]=dmin[vfmin]+G[vfmin][j].c;
					prec[G[vfmin][j].vf]=vfmin;
					if (poz[G[vfmin][j].vf]==-1)
						InsertHeap(G[vfmin][j].vf);
					   else
						Upgrade(poz[G[vfmin][j].vf]);
					}
	
	}
}


void InsertHeap(int vf)
{h[++lgh]=vf; Upgrade(lgh);}

void Upgrade(int fiu)
{
int tata=fiu/2, aux;
while (tata && dmin[tata]>dmin[fiu])
	{
	poz[h[fiu]]=tata; poz[h[tata]]=fiu;	
    aux=h[fiu]; h[fiu]=h[tata]; h[tata]=aux; 
	fiu=tata;
	tata=fiu/2;
	}
}

int ExtractMin()
{int fiu, tata, aux;
int minim=h[1];
h[1]=h[lgh--]; poz[h[1]]=-1;
//downgrade
tata=1; fiu=2*tata;
while (fiu<=lgh)
	  {
	   if (fiu<lgh && dmin[h[fiu]]>dmin[h[fiu+1]]) fiu++;
	   if (dmin[h[tata]]>dmin[h[fiu]])
		   {
	       poz[h[fiu]]=tata; poz[h[tata]]=fiu;	
           aux=h[fiu]; h[fiu]=h[tata]; h[tata]=aux; 
		   tata=fiu;
		   fiu=tata*2;
		   }
		   else break;
		}
return minim;
}

void afisare()
{
ofstream fout(OutFile);
int i;
for (i=1; i<=n; i++)
	if (i!=x0)
		if (dmin[i]!=INF) fout<<dmin[i]<<' ';
			else
			fout<<0<<' ';
fout.close();			

}