#include <iostream>
#include<fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int max1=9999999,a[100][100],i,j,n,m,c;
int d[100],t[100],s[100],minim,poz;
int main()
{
   f>>n>>m;
   for(i=1;i<=n;++i)
    for(j=1;j<=m;++j)
       if(i==j)
        a[i][j]=0;
       else
        a[i][j]=max1;
   while(f>>i>>j>>c)
   {
       a[i][j]=c;
   }
   s[m]=1;
   for(i=1;i<=n;++i)
   {
       d[i]=a[m][i];
       if(i!=m)
       if(d[i]<max1)
       t[i]=m;
   }
   for(i=1;i<=n-1;++i)
   {
       minim=max1;
       for(j=1;j<=n;++j)
        if(s[j]==0)
        if(d[j]<minim)
       {
           minim=d[j];
           poz=j;
       }
   s[poz]=1;
   for(j=1;j<=n;++j)
    if(s[j]==0)
    if(d[j]>d[poz]+a[poz][j])
   {
       d[j]=d[poz]+a[poz][j];
       t[j]=poz;
   }
   }
for(i=1;i<=n;++i)
    if(d[i]<max1)
    g<<d[i]<<" ";
else
    g<<-1<<" ";
    return 0;
}