#include <stdio.h>

int main()
{
    int number_of_vertices = 0;
    int number_of_faces = 0;
    int infinity = 10000;
    scanf("%d", &number_of_vertices);
    scanf("%d", &number_of_faces);
    int x, y, length;
    int way[number_of_vertices][number_of_vertices];
    int attendance[number_of_vertices];
    int the_shortest_way[number_of_vertices];

    for (int i = 1; i <= number_of_vertices; i++)
    {
        for (int j = 1; j <= number_of_vertices; j++)
        {
            way[i][j] = 0;
        }
    }
    for (int i = 1; i <= number_of_faces; i++)
    {
        scanf("%d%d%d", &x, &y, &length);
        way[x][y] = length;
        way[y][x] = length;
    }
    for (int i = 1; i <= number_of_vertices; i++)
    {
        for (int j = 1; j <= number_of_vertices; j++)
        {
            printf("%3d ",way[i][j]);
        }
    printf("\n");
    }

    for (int i = 1; i <= number_of_vertices; i++)
    {
        attendance[i] = 0;
    }

    for (int i = 1; i <= number_of_vertices; i++)
    {
        the_shortest_way[i] = infinity;
    }

    int element;
    scanf("%d", &element);

    the_shortest_way[element] = 0;

    for (int i = 1; i <= number_of_vertices; i++)
    {
        printf("%d ",the_shortest_way[i]);
    }

    int temp;
    int minindex;
    int min;
    do {
    minindex = infinity;
    min = infinity;
    for (int i = 1; i <= number_of_vertices; i++)
    {
      if ((attendance[i] == 0) && (the_shortest_way[i] < min))
      {
        min = the_shortest_way[i];
        minindex = i;
      }
    }
    if (minindex != infinity)
    {
      for (int i = 1; i <= number_of_vertices; i++)
      {
        if (way[minindex][i] > 0)
        {
          temp = min + way[minindex][i];
          if (temp < the_shortest_way[i])
          {
            the_shortest_way[i] = temp;
          }
        }
      }
      attendance[minindex] = 1;
    }
  } while (minindex < 10000);
  printf("\nКратчайшие расстояния до вершин: \n");
  for (int i = 1; i <= number_of_vertices; i++)
    printf("%d ", the_shortest_way[i]);
    return 0;
}