#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <int> graf[50];
int mat[50][50];
int viz[50];
int main()
{
    int n,m,a,b,c,i,j,x,k=0;
    fin>>n>>m;
    while(k<m)
    {
        fin>>i>>j>>x;
        mat[i][j]=x;
        k++;
    }
    int dis[50];
    for(i=0;i<=n;i++)
    {
        dis[i]=9999;
    }
    k=0;
    cout<<"introudceti nodul de la care vrei sa aflati distanta minima:"<<endl;
    int index;
    cin>>index;
    int minim=0;
    for(i=1;i<=n;i++)
        {

            if(mat[index][i]!=0&&dis[i]>mat[index][i])
            {
                viz[i]=1;
                dis[i]=mat[index][i];
                for(j=1;j<=n;j++)
                {
                    if(mat[i][j]!=0&&viz[j]==0)
                        {
                            dis[j]=dis[i];
                            dis[j]=dis[j]+mat[i][j];
                            viz[j]=1;
                        }
                }
            }
        }
      for(i=2;i<=n;i++)
        fout<<dis[i]<<" ";

    /*for(i=1;i<=n;i++)
     {
        for(j=1;j<=n;j++)
            {
                cout<<mat[i][j]<<" ";
            }
            cout<<endl;

    }
*/
    fin.close();
    fout.close();
    return 0;
}