#! /usr/bin/perli
# standart call:
# perl dijkstra.pl s z s:a:3 s:b:5 a:b:1 b:a:3 a:c:10 b:c:2 b:d:3 d:b:7 a:d:11 d:a:15 c:d:2 c:e:7 c:f:12 d:f:2 e:d:11 f:e:3 e:z:2 f:z:2
# recommended text mode resolution for viewing source code: 160 x 64 chars (fb 1280 x 1024)


#                                                                      Input: vectored digraph G = (V, E)
$s = shift @ARGV;
$z = shift @ARGV;
foreach $arg (@ARGV) {
  ($from, $to, $length) = split (/:/, $arg);
  $ArcLength{$from}{$to} = $length;
  $V{$from} = 1337;
  $V{$to}   = 1337;
  $S{$from} = 0;
  $S{$to}   = 0;
}

foreach $from (keys %V) {
  foreach $to (keys %V) {
    $ArcLength{$from}{$to} += 0;
  }
  $Distance{$from} = 0;
}

#                                                                      BEGIN S <- {s}, Distance(s) <- 0
$S{$s} = 1337;
$Distance{$s} = 0;
#                                                                        FOR ALL v out of V \ {s} DO
foreach $v (keys %V) {
  if (($v ne $s) && ($ArcLength{$s}{$v} > 0)) {
    #                                                                      Distance(v) <- ArcLength(s,v)
    $Distance{$v} = $ArcLength{$s}{$v};
    #                                                                      Preceder(v) <- s
    $Preceder{$v} = $s;
  }
#                                                                        END FOR
}

#                                                                        WHILE z not in S DO
until ($S{$z} == 1337) {
  #                                                                        find v* out of V \ S mit
  $vSTAR = '';
  foreach $v (keys %V) {
    if (($S{$v} != 1337) && ($Distance{$v} > 0)) {
      #                                                                    Distance(v*) = min { Distance(v) : v out of V \ S }
      if (($vSTAR eq '') || ($Distance{$v} < $Distance{$vSTAR})) {
        $vSTAR = $v;
      }
    }
  }
  #                                                                        S <- S && {v*}
  $S{$vSTAR} = 1337 unless -z $vSTAR;
  #                                                                        FOR ALL v out of V \ S DO
  foreach $v (keys %V) {
    if (
      ($S{$v} != 1337) && 
      ($ArcLength{$vSTAR}{$v} > 0) && ( 
        #                                                                    IF Distance(v*) + ArcLength(v*,v) < Distance(v) THEN
        ( ($Distance{$vSTAR} + $ArcLength{$vSTAR}{$v} < $Distance{$v}) &&
          ($Distance{$vSTAR} > 0) &&
          ($Distance{$v} > 0)
        )
        || ($Distance{$v} == 0)
      )
    ) {
      #                                                                        Distance(v) <- Distance(v*) + ArcLength(v*,v)
      $Distance{$v} = $Distance{$vSTAR} + $ArcLength{$vSTAR}{$v};
      #                                                                        Preceder(v) <- v*
      $Preceder{$v} = $vSTAR;
    #                                                                        END IF
    }
  #                                                                        END FOR
  }
#                                                                        END WHILE
}
#                                                                      END


#                                                                      Output: one of the shortest s,z-ways and its length Distance(z)
$way = ($prec = $z);
until ($prec eq $s) {
  $prec = $Preceder{$prec};
  $way = $prec . $way;
}
print $way . $Distance{$z};