require 'set'

class Heap
    def initialize
        @array = []
        @index = {}
    end

    def empty?
      @array.empty?
    end

    def add(obj, key)
        if @index[obj]
          return update(obj, key)
        end
        @array << [obj, key]
        @index[obj] = @array.size - 1
        lift_up(@array.size - 1)
    end

    def swap(i, j)
        u = @array[i]
        v = @array[j]
        @index[u[0]], @index[v[0]] = j, i
        @array[i], @array[j] = v, u
    end

    def lift_up(i)
        return if i == 0
        j = (i - 1) / 2
        if @array[i][1] < @array[j][1]
            swap(i, j)
            lift_up(j)
        end
    end

    def del_min
        raise "heap is empty!" if empty?
        min = @array[0]
        if @array.size > 1
            swap(0, @array.size - 1)
            @array.pop
            lift_down(0)
        else
            @array.pop
        end
        @index.delete(min[0])
        min
    end

    def update(obj, new_key)
        i = @index[obj]
        return unless i
        old_key = @array[i][1]
        return if old_key <= new_key
        @array[i][1] = new_key
        if new_key > old_key
            @array[i][1] = new_key
            lift_down(i)
        else
            @array[i][1] = new_key
            lift_up(i)
        end
    end

    def lift_down(i)
        j = 2 * i + 1
        k = j + 1
        if k >= @array.size
            return if j >= @array.size
            if @array[i][1] > @array[j][1]
                swap(i, j)
                lift_down(j)
            end
        else
            l = (@array[j][1] < @array[k][1] ? j : k)
            if @array[i][1] > @array[l][1]
                swap(i, l)
                lift_down(l)
            end
        end
    end
end

loop do
  n, m, c = gets.split.map(&:to_i)
  break if n == 0

  orig_graph = {}
  (0..n-1).each do |i|
    orig_graph[i] = {}
  end
  m.times do
    i, j, w = gets.split.map(&:to_i)
    i -= 1
    j -= 1
    orig_graph[i][j] = w
  end

  graph = Marshal.load(Marshal.dump(orig_graph))
  (1..n-1).each do |k|
    (0..n-1).each do |i|
      graph[k * n + i] = {}
      orig_graph[i].each do |j, w|
        graph[(k - 1) * n + i][k * n + j] = 0
        graph[k * n + i][k * n + j] = w
      end
    end
  end

  # Dijkstra
  pq = Heap.new
  pq.add(0, 0)
  fixed = Set.new
  dist = { 0 => 0 }
  until pq.empty?
    i, d = pq.del_min
    fixed << i
    dist[i] = d
    graph[i].each do |j, w|
      next if fixed.include?(j)
      pq.add(j, d + w)
    end
  end

  (1..n).each do |k|
    i = k * n + n - 1
    if dist[i] < c
      puts k
      break
    end
  end
end

