<?php
$fi = fopen( "input.txt", "r");    // відкривання файлу в режимі читання
$fo = fopen("output.txt", "w");    // відкривання файлу в режимі запису
[$nv, $ne] = explode(" ", trim(fgets($fi)), 2);
$nv = (int) $nv;  // кількість вершин
$ne = (int) $ne;  // кількість ребер
$b  = array();    // списки суміжності
$w  = array();    // ваги ребер
$c  = array();    // ознака сталості
$p  = array();    // попередники
$l  = array();    // попередники
$l_max = 999999;  // обмеження зверху на довжину
for ($k=0; $k < $nv; $k++)
{ $b[] = array();
  $w[] = array();
  $c[] = false;
  $l[] = $l_max;
  $p[] = 0;
}

for ($i=0; $i < $ne; $i++)
{[$j, $k, $u] = explode(" ", trim(fgets($fi)), 3);
 $j = (int) $j;
 $k = (int) $k;
 $u = (int) $u;
 $b[$j][] = $k;
 $w[$j][] = $u;
 $b[$k][] = $j;
 $w[$k][] = $u;
}
fclose($fi);

function step ($j)
{ global $b,$c,$l,$nv,$p,$w,$l_max;
  for ($i=0; $i< count($b[$j]); $i++)
  { if (!$c[$b[$j][$i]])
    { $s = $l[$j] + $w[$j][$i];
      if ($l[$b[$j][$i]] > $s)
      {   $l[$b[$j][$i]] = $s;
          $p[$b[$j][$i]] = $j;
      }
    }
  }

  $s = $l_max;
  for ($k=0; $k < $nv; $k++)
  { if (!$c[$k])
    { if ($s > $l[$k])
      { $s = $l[$k];
        $i = $k;
      }
    }
  }
  $c[$i] = true;

  return $i;
}  
$start   = 0;             // Номери вершин,
$finish  = $nv-1; // між якими шукаємо шлях
$c[$start] = true;
$l[$start] = 0;
$j = $start;

while ($j!=$finish) $j=step($j);
                              // Запис у вихідний файл
fwrite($fo,$l[$finish]."\n"); // 1) довжини найкоротшого шляху;
$j = $finish;                 // 2) послідовнисті номерів вершин шляху у зворотньому порядку
$o = $j;         
while ($j!=$start)
{ $j = $p[$j];
  $o = $o." $j";
}
fwrite($fo,$o."\n");
fclose($fo);
echo "Все зроблено!";
?>