
class Entry
  attr_reader :size, :value
 
  def initialize(size, value)
    @size = size
    @value = value
  end
end
 
class PrefixQueue
  def initialize
    @list = []
    @prefix = ''
  end
 
  def empty?
    @list.empty?
  end
 
  def shift
    entry = @list.shift
    [@prefix[0...entry.size], entry.value]
  end
 
  def push(key, value)
    (0...@list.size).each do |i|
      entry = @list[i]
      target = @prefix[0...entry.size]
      case target <=> key
      when -1
        return nil unless key.start_with?(target)
      when 0
        return entry.value
      else
        if target.start_with?(key)
          @list.insert(i, nil)
        else
          @prefix = key
          @list.slice!(i+1..-1)
        end
        @list[i] = Entry.new(key.size, value)
        return value
      end
    end
    @prefix = key
    @list << Entry.new(key.size, value)
    return value
  end
end

class Arrow
  attr_reader :source, :sink, :label

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

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

  reachable_from = [false] * n
  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]

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

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

    return nil if spell.size > 500

    map.each do |node, tainted|
      go[node].each do |arrow|
        t = queue.push(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