uses crt;

var
  a,b,h,e:Real;
  x1,x2,x:Real;
  g:Text;

function Fun(x:Real):Real;
begin
  Fun:=x*sin(x)-1;
end;

function Root(x1,x2,e:Real):Real;
var
  x:Real;
begin

 while (x2-x1)>=e do
  begin
    x:=(x1+x2)/2;
    if Fun(x1)*Fun(x)<0 then x2:=x else x1:=x;
  end;
  Root:=(x1+x2)/2;
end;

begin
  a:=-40;b:=40;h:=0.1;e:=0.000001;
  x1:=a;x2:=a+h;
  Assign(g,'D:\Korny.txt');
  Rewrite(g);
  ClrScr;
  while x2<=b do
  begin
    if Fun(x2)=0 then
      begin
 Writeln('Found x=',x2:6:2);
 Writeln(g,'Root=',x2:6:6);
      end
    else if 
 Fun(x1)*Fun(x2)<0 then
  begin
    Writeln('[',x1:6:2,';',x2:6:2,']');
    x:=Root(x1,x2,e);
    Writeln(g,'Root=',x:6:6);
  end;
    x1:=x2;
    x2:=x2+h;
  end;
  Close(g);
  Readln;
end.

var
 Q:array[1..100] of byte;   {очередь}
 left,right:byte;
procedure Enqueue(x:word); {процедура добавления в очередь вершины}
begin
  Q[right]:=x;
  if right=100
then right:=1 else inc(right);
end;

procedure Dequeue;              {процедура удаления из очереди вершины}
begin
  if left=100 then left:=1 else inc(left);
end;
var
 G:array[1..100,1..100] of word;  {граф}
 i,j,k,h:word;
 d:array[1..100] of word;             {массив расстояний}
 p:array[1..100] of word;             {массив предков}
 color:array[1..100] of byte;         {массив цветов}
 n:word;
 fin:text;
 beg:word;      
                              {начальная вершина}
begin
 k:=0;
{чтение графа из файла, имя которого - первый параметр командной строки} 
 assign(fin,paramstr(1)); reset(fin);
 read(fin,n); readln(fin,beg);
 while not EOF(fin) do
   begin
     read(fin,i); readln(fin,j);
     g[i,j]:=1; g[j,i]:=1;
   end;
 close(fin);
{конец чтения из файла}
{инициализация массивов}
 for i:=1 to n do
   begin
     color[i]:=0;
     d[i]:=65535;
     p[i]:=0;
   end;
{конец
инициализации массивов}
color[beg]:=1;
d[beg]:=0;
p[beg]:=0;
left:=1;
right:=1;
Enqueue(beg);             {добавление первой вершины в очередь}
while left<>right do      {пока очередь не пуста}
  begin
    k:=Q[left];
    for i:=1 to n do        {для всех вершин...}
      if g[k,i]=1 then       {...смежных с k...}
      begin
        if color[i] = 0 then {...если мы ее еще не обрабатывали...}
          begin
       
      color[i]:=1;       {...сделать цвет серым...}
            d[i]:=d[k]+1;    {...указать расстояние...}
            p[i]:=k;             {...указать предка...}
            EnQueue(i);      {...добавить в очередь}
          end;
      end;
    Dequeue;                {удалить из очереди}
    color[k]:=2;             {сделать цвет черным: вершина полностью обработана}
  end;
{вывод на экран расстояния от s до всех вершин, достигаемых из нее}
for i:=1 to n do
  write(d[i],'
');
  writeln;
end.

var
 fin:text;
 g:array[1..100,1..100] of word;           {матрица смежности}
 N:word;
 d,f:array[1..100] of word;                    {массивы меток}
 p:array[1..100] of wo
 rd;                      {массив предков}
 color:array[1..100] of byte;                 {массив цветов}
 time:word;                                           {счетчик времени}
procedure DFS_visit(u:word);
var
  i,j:word;
begin
  color[u]:=1;                                        {"окрашиваем"вершину u в серый цвет}
  inc(time);
  d[u]:=time;
  for i:=1 to n do 
    if g[u,i]=1 then                                 {Если есть ребро из u в i...}
      if color[i]=0
then                             {... то если цвет i белый (мы ее еще не обрабатывали)...}
        begin
          p[i]:=u;                                       {...предок i - v...}
          DFS_Visit(i);                                {...вызываем рекурсивно процедуру для вершины i}
        end;
                                                             {после выполнения цикла мы гарантируем, что обработали                                             
                     все смежные u необработанные вершины}
  color[u]:=2;                                        {помечаем u как обработ
анную}
  inc(time);
  f[u]:=time;
end;
var
  i,j:word;
begin
 {читаем информацию про граф из файла, заданного первым параметром командной строки}
 {граф задан так: первая строка файла - колличество вершин. В каждой следующей строке - два числа i и j. Это означает, что в графе существует ребро i->j}
 assign(fin,paramstr(1)); reset(fin);
 readln(fin,n);
 while not EOF(fin) do
   begin
     read(fin,i); readln(fin,j);
     g[i,j]:=1;
   end;
 close(fin);
 {граф
прочитан}
 {обнуляем массивы предков и цветов}
 for i:=1 to n do
   begin
     color[i]:=0;
     p[i]:=0;
   end;
 for i:=1 to n do
   if color[i]=0 then
     DFS_Visit(i);
 {в этот момент построенно дерево поиска, которое находится в массиве p, известно, на каком шаге каждая вершины вошла в поиск. Эту информацию можно использовать как данные для других алгоритмов}
end.

program HS;
uses new_crt;
 type
     CM    = array[1..100, 1..100] of integer;
     StArr = array[1..100] of
integer;
     NnewA = array[1..100] of boolean;
 var St:  StArr;
     Nnew:NnewA;
     A:   CM;
     i, N, M:integer;
     f: text;
function ReadArr(S: string; var A: CM; var k:  integer):boolean;
 var f:    text;
     i, j, l: integer;
     c: integer;
  begin
    assign(f, S);
    reset(f);
      i:=1; j:=1;
      while not eof(f) do
        begin
          while not eoln(f) do
            begin
              read
 (f, c);
              a[i, j]:=c;
              j:=j+1;
            end;
          i:=i+1; l:=j-1; j:=1;
          readln(f);
        end;
    close(f);
    k:=i-1;
    if (k=l) then ReadArr:=true
             else ReadArr:=false;
  end;
procedure Gm(k: integer);
 var j,v: integer;
     f:   text;
     i:   integer;
  begin
    v:=St[k-1];
    assign(f, 'output.txt');
    rewrite(f);
    for j:=1 to N do begin
      write(A[v,j], ' ');

     if (A[v,j]<>0) then begin
        if (k=N+1) and (j=1) then for i:=1 to k do write(f, St[i], ' '); end
                             else if Nnew[j] then begin
                               St[k]:=j;
                               Nnew[j]:=false;
                               writeln(f);
                               Gm(k+1);
                               Nnew[j]:=true;
                             end;
    end; w
 riteln;
    close(f);
  end;
begin
clrscr;
  if ReadArr('input.txt', A, N) then begin
       Writeln(N);
       St[1]:=1;
       Nnew[1]:=false;
       Gm(2);
  end;
repeat until keypressed;
end.

const
   inp='graph.in';
   ou='graph.out';
   maxn=100;

var
   ist,n:integer;
   c:array [1..maxn,1..maxn] of integer;
   dist:array [1..maxn] of integer;

{Ввод
данных. В файле 'graph.in' - число вершин графа n и матрица смежности c;
c[i,j]=max, если дуги из i в j нет; предпологается, что max - некоторое число,
много большее веса ребер графа; ist - номер вершины источника}
procedure Init;
var
   i,j:integer;
begin
assign (input,inp);
reset (input);
read (n);
for i:=1 to n do
   for j:=1 to n do
      read (c[i,j]);
read (ist);
close (input)
end;

function min(a,b:integer):
 integer;
begin
if a<b then min:=a else min:=b
end;

{Вычисление кратчайших путей}
procedure FordBellman(ist:integer);
var
   i,j,count:integer;
begin
for i:=1 to n do
   dist[i]:=c[ist,i];
count:=1;
while count<n do
   begin
   for i:=1 to n do
      for j:=1 to n do
         dist[i]:=min(dist[i],dist[j]+c[j,i]);
   inc(count)
   end
end;

{Вывод результата; i-ое число - кратчайшее расстояние от вершины ist до
вершины i; если это число
равно max, пути нет}
procedure PrintResult;
var
   i:integer;
begin
assign (output,ou);
rewrite (output);
for i:=1 to n do
   write (dist[i],' ');
close (output)
end;

begin
Init;
FordBellman(ist);
PrintResult
end.

Uses Crt,Graph,Graphs;
Const
   M=19;            {Предельное число вершин графа}
   R=200;              {Радиус окружности на которой лежат вершины (центры окружностей)}
Type
   Dmas = Array[1..M,1..M] Of Integer;
Var
   N,            {Число вершин графа}
   I,J,
   Nac,          {Номер начальной вершины}
   Kon: Integer;         {Номер конечной вершины}
   T,            {Матрица, хранящая длины
путей}
   H,            {Матрица, хранящая пути}
   C: Dmas;      {Матрица, хранящая длины дуг}
 
{Процедуры используемые в программе}

 Procedure Dlina;      {Процедура задания матрицы длин дуг}
 
 Begin
 GotoXY(7,7);
 Write('Введите число вершин графа: ');
 Readln(N);        {Задание значения числа вершин}
 If N>M Then Halt;         {Если вершин больше чем константа M, то выход из программы}
 Clrscr;         {Очистка экра
 на}
  If N>5 Then          {Автоматическое задание значений длин дуг}
    For I:=1 To N Do
      For J:=1 To N Do
      If I=J Then C[I,J]:=0
        Else C[I,J]:=Random(100)+1         {Генерация текущего значения}
    Else
     Begin           {Задание длин дуг вводом с клавиатуры}
       For I:=1 To N Do
         Begin
          Writeln;
          For J:=1 To N Do
           If I<>J Then
             Begin
               Write('Введите вес дуги [',I,',',J,']:=
');
               Readln(C[I,J])          {Ввод с клавиатуры значения длины дуги}
             End
           Else If I=J Then C[I,J]:=0;
          End
       End;
  {Вывод полученной матрицы дуг}
  Clrscr;          {Очистка экрана}
  Writeln('Матрица длин дуг');
  Writeln;
  Write('   ');
  TextColor(Green);       {Задание цвета текста}
  For I:=1 To N Do
    Write('  ',Chr(64+I)
 ,' ');
  Writeln;
  For I:=1 To N Do
    Begin
      TextColor(Green);        {Задание цвета текста}
      Write(&#
39; ',Chr(64+I),' ');
      TextColor(White);        {Задание цвета текста}
     For J:=1 To N Do
       Write(C[I,J]:3,' ');           {Вывод текущего элемента матрицы}
      Writeln
    End;
  Readln        {Задержка экрана}
  End;

  Procedure Floid;           {Процедура нахождения кратчайших путей и их длин}
  
  Var
     I,J,K: Integer;
  Begin
    For I:=1 To N Do
      For J:=1 To N Do
       Begin
         T[I,J]:=C[I,J];        {Начальная
установка длин путей}
         If C[I,J]=100 Then
            H[I,J]:=0         {Нет дуги из вершины "I" в "J" вершину}
         Else
            H[I,J]:=J          {Есть дуга из вершины "I" в "J" вершину}
       End;
    For I:=1 To N Do
     Begin
      For J:=1 To N Do
        For K:=1 To N Do
         If (I<>J) And (T[J,I]<>100) And (I<>K) And (T[I,K]<>100)
      
       And ((T[J,K]=100) Or (T[J,K]>T[J,I]+T[I,K])) Then
             Begin
               H[J,K]:=I;         {Запоминаем новый путь}
               T[J,K]:=T[J,I]+T[I,K]       {Запоминаем длину данного нового пути}
             End;
      For J:=1 To N Do
        If T[J,J]<0 Then Break      {Нет решения: вершина входит в цикл отрицательной длины}
     End;
  {Вывод полученной матрицы путей}
  Clrscr;         {Очистка экрана}
  Writeln('Матрица путей');
  Writeln;

 Write('   ');
  TextColor(Green);       {Задание цвета текста}
  For I:=1 To N Do
    Write('  ',Chr(64+I),' ');
  Writeln;
  For I:=1 To N Do
    Begin
      TextColor(Green);       {Задание цвета текста}
      Write(' ',Chr(64+I),' ');
      TextColor(White);       {Задание цвета текста}
     For J:=1 To N Do
       Write(H[I,J]:3,' ');          {Вывод текущего элемента матрицы}
 
      Writeln
    End;
  Readln;         {Задержка экрана}
  {Вывод полученной матрицы длин путей}
  Clrscr;         {Очистка экрана}
  Writeln('Матрица длин путей');
  Writeln;
  Write('   ');
  TextColor(Green);         {Задание цвета текста}
  For I:=1 To N Do
    Write('  ',Chr(64+I),' ');
  Writeln;
  For I:=1 To N Do
    Begin
      TextColor(Green);        {Задание цвета текста}
      Write(' ',Chr(64+I),' ');

     TextColor(White);        {Задание цвета текста}
     For J:=1 To N Do
       Write(T[I,J]:3,' ');         {Вывод текущего элемента матрицы}
      Writeln
    End;
  Readln;         {Задержка экрана}
  Clrscr;        {Очистка экрана}
  GotoXY(10,10);
  Write('Введите номер начальной вершины пути: '); Readln(Nac);
  GotoXY(10,12);
  Write('Введите номер конечной вершины пути: '); Readln(Kon);
  Writeln;
  
 Write('Длина пути из вершины ',Chr(64+Nac),' в вершину ',Chr(64+Kon),' равна: ',T[Nac,Kon]);
  Readln         {Задержка экрана}
  End;

  Procedure Koordinata;         {Процедура вывода найденных значений}
  
 Var
   Q,W: Real;
     K: Char;
     X1,X2,Y1,Y2,
     X: Integer;
 Begin
     Open_Graph;         {Подключение графического режима}
  Q:=2*Pi/N;          {Установка значения угла между границами сектора}
  {Задание координат вершин графа}

 For I:=1 To N Do
    Begin
     W:=I*Q;          {Установка текущего угла}
     {Установка координат}
      X1:=300+Trunc(R*cos(W)); Y1:=235+Trunc(R*sin(W));
      X2:=300+Trunc((R+25)*cos(W)); Y2:=235+Trunc((R+25)*sin(W));
      K:=Chr(64+I);        {Задание текущего названия вершины}
      SetColor(White);       {Задание цвета названий вершин}
     OutTextXY(X2,Y2,K);       {Вывод названия вершины}
      SetColor(Green);         {Задан
 ие цвета вершины}
      For J:=1 To 7 Do
       Circle(X1,Y1,J)          {Вывод концентрических окружностей для задания вершины на э
кране}
      End;
    {Вывод кратчайшего пути}
      X:=Nac;
        W:=Q*Nac;        {Установка текущего угла}
        {Установка координат}
        X1:=300+Trunc(R*cos(W)); Y1:=235+Trunc(R*sin(W));
        SetColor(Red);
        PutPixel(X1,Y1,Red);
         Repeat
           X:=H[X,Kon];        {Переход на следующую вершину в пути}
           W:=Q*X;          {Установка текущего угла}
           {Установка координат}
           X2:=300+Trunc(R*cos(W)); Y2:=235+Trunc(R*sin(W));

          Line(X1,Y1,X2,Y2);
           X1:=X2;
           Y1:=Y2
         Until X=Kon;
      SetColor(White);
      OutTextXY(3,450,'Press any key, please...');
      Readln;      {Задержка экрана}
      Close_Graph;       {Отключение графического режима}
      Clrscr
    End;
 
Begin

 ClrScr;     {Очистка экрана}
 TextBackGround(Black);      {Задание цвета фона}
 TextColor(White);          {Задание цвет
 а текста}
  Clrscr;
  Dlina;       {Задание длин дуг}
  Floid;       {Поиск кратчайшего пути и его длины}
  Koordinata       {Вывод найденных значений}
End.

const
  maxn = 100;
  infinity = maxlongint;

var

 i,j,u,v,n,m,c,min,s,t:longint;
  e,w:array[1..maxn,1..maxn]of longint;
  ne,use,p,d:array[1..maxn]of longint;

begin
  read(n,m,t,s);
  for i:=1 to m do begin
    read(u,v,c);
    inc(ne[v]); e[v,ne[v]]:=u; //edges are inverted
    w[v,u]:=c;
  end;
  for i:=1 to n do d[i]:=infinity;
  d[s]:=0;
  for i:=1 to n do begin
    min:=infinity;
    for j:=1 to n do if (use[j]=0)and(d[j]<min) then begin
      min:=d[j]; u:=j;<
 br>    end;
    use[u]:=1;
    for j:=1 to ne[u] do begin
      v:=e[u,j];
      if d[v]>d[u]+w[u,v] then begin
        d[v]:=d[u]+w[u,v]; p[v]:=u;
      end;
    end;
  end;
  writeln(d[t]);
  u:=t; write(u);
  while u<>s do begin
    u:=p[u]; write(' ',u);
  end;
end.