import sys
import collections
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    M = int(input[ptr]); ptr +=1
    K = int(input[ptr]); ptr +=1
    L = int(input[ptr]); ptr +=1
    
    edges_by_z = defaultdict(list)
    for _ in range(L):
        X = int(input[ptr])-1; ptr +=1
        Y = int(input[ptr])-1; ptr +=1
        Z = int(input[ptr]); ptr +=1
        edges_by_z[Z].append( (X, Y) )
    
    sorted_zs = sorted(edges_by_z.keys(), reverse=True)
    used_X = set()
    used_Y = set()
    total = 0
    
    for z in sorted_zs:
        edges = []
        for X, Y in edges_by_z[z]:
            if X not in used_X and Y not in used_Y:
                edges.append( (X, Y) )
        if not edges:
            continue
        
        graph = defaultdict(list)
        for X, Y in edges:
            graph[X].append(Y)
        
        for X in graph:
            graph[X].sort(reverse=True)  # Reverse to process higher Y first
        
        match_to_Y = {}
        match_to_X = {}
        layers = {}
        
        def bfs():
            layers.clear()
            queue = collections.deque()
            for X in graph:
                if X not in match_to_X:
                    layers[X] = 0
                    queue.append(X)
            res = False
            while queue:
                X = queue.popleft()
                for Y in graph[X]:
                    if Y not in match_to_Y:
                        res = True
                    else:
                        if match_to_Y[Y] not in layers:
                            layers[match_to_Y[Y]] = layers[X] + 1
                            queue.append(match_to_Y[Y])
            return res
        
        def dfs(X):
            for Y in graph[X]:
                if Y not in match_to_Y or (match_to_Y[Y] in layers and layers[match_to_Y[Y]] == layers[X] + 1 and dfs(match_to_Y[Y])):
                    match_to_X[X] = Y
                    match_to_Y[Y] = X
                    return True
            layers[X] = -1
            return False
        
        result = 0
        while bfs():
            new_matches = 0
            for X in list(graph.keys()):
                if X not in match_to_X:
                    if dfs(X):
                        new_matches += 1
            result += new_matches
        
        for X in match_to_X:
            Y = match_to_X[X]
            used_X.add(X)
            used_Y.add(Y)
            total += (1 << z)
    
    print(total)

if __name__ == "__main__":
    main()