
 
class Arrow
  attr_reader :source, :sink, :label

  def initialize(source, sink, label)
    @source = source
    @sink = sink
    @label = label
  end
end

def push(queue, key, value)
  index = queue.index{|target, _| target >= key}
  return queue[index][1] if index && queue[index][0] == key
  return nil if index && index > 0 && !key.start_with?(queue[index - 1][0])
  queue.slice!(index..-1) if index && !queue[index][0].start_with?(key)
  queue.insert(index || queue.size, [key, value])
  value
end

def collect(n, arrows, goal)
  come_from = Array.new(n){[]}
  arrows.each do |arrow|
    come_from[arrow.sink] << arrow.source
  end

  reachable_from = {}
  stack = [goal]
  until stack.empty?
    node = stack.pop
    reachable_from[node] = true
    come_from[node].each do |source|
      stack << source unless reachable_from[source]
    end
  end
  reachable_from
end

def work(n, arrows, start, goal)
  reachable_from = collect(n, arrows, goal)
  return nil unless reachable_from[start]
  arrows.select!{|arrow| reachable_from[arrow.sink]}

  go = Array.new(n){[]}
  arrows.each do |arrow|
    go[arrow.source] << arrow
  end

  max = n * arrows.map{|arrow| arrow.label.size}.max

  queue = [['', {start => true}]]
  until queue.empty?
    spell, map = queue.shift
    return spell if map[goal]

    return nil if spell.size > max

    map.each do |node, unused|
      go[node].each do |arrow|
        t = push(queue, spell + arrow.label, {})
        t[arrow.sink] = true if t
      end
    end
  end
  nil
end

loop do
  n, a, s, g = gets.split.map(&:to_i)
  break if n == 0

  arrows = (0...a).map do |i|
    x, y, lab = gets.split
    Arrow.new(x.to_i, y.to_i, lab)
  end

  puts work(n, arrows, s, g) || 'NO'
end