from sys import stdin
import sys
import re

nm = stdin.readline()
sk = stdin.readline()

number = r"[1-9][0-9]*"
two_numbers = f"{number} {number}$"

# 2 lines of 2 space-separated integers
assert re.match(two_numbers, nm)
assert re.match(two_numbers, sk)

n, m = map(int, nm.split())
s, k = map(int, sk.split())

minn, maxn = 2, 30
assert minn <= n <= maxn

minm, maxm = n-1, 500
assert minm <= m <= maxm

mink, maxk = 1, 1e4
assert 1 <= s <= k <= 1e4

for _ in range(m):
    machine = stdin.readline()

    three_numbers = f"{number} {number} {number}$"
    assert re.match(three_numbers, machine)

    i, m_i, m_o = map(int, machine.split())

    assert 1 <= i <= n-1

    assert 1 <= m_i <= maxk
    assert 1 <= m_o <= maxk

assert len(stdin.readline()) == 0

sys.exit(42)