소프티어

런타임에러/오답/시간초과 반례 하나씩만 부탁드립니다!

n, m = map(int, input().split())

alpha = []
beta = []
graph = [[] for i in range(n+1)]
for i in range(m):
    alpha.append(list(map(int, input().split())))
    
for i in range(m):
    if alpha[i][0] > alpha[i][1]:
        q = alpha[i][0]
        alpha[i][0] = alpha[i][1]
        alpha[i][1] = q
        
for i in range(m):
    for j in range(m):
        if i != j and alpha[i][0] == alpha[j][0] and alpha[i][1] == alpha[j][1]:
            if alpha[i][2] > alpha[j][2]:
                beta.append(i)
            else :
                beta.append(j)
beta_s = set(beta)
beta = list(beta_s)
beta.sort()

x = 0
for i in range(len(beta)):
    del alpha[beta[i]-x]
    x += 1
m = len(alpha)
for i in range(1,n+1):
    for j in range(len(alpha)):
        if alpha[j][0] == i:
            graph[i].append((alpha[j][1],alpha[j][2]))
level = [0]*(n+1)
index = 0
array = []
x = 1
stop = 1
a = 0

while stop == 1:

    if len(graph[x]) != 0:
        for j in graph[x]:
            if level[j[0]] < j[1]:
                level[j[0]] = j[1]+1

            if level[j[0]] < a:
                level[j[0]] = a

        for k in range(n,0,-1):    
            if level[k] != 0:
                a = level[k]
                level[k] = 0
                x = k

                break
        if x == n:
            array.append(a)
            for s in range(n,0,-1):
                if level[s] !=0:
                    x = s
                    a = level[s]
                    level[s] = 0 
                    break
                if s == 1:
                    stop = 0
                    break
    else :
        for w in range(n,0,-1):
            if level[w] !=0 and w != x:
                a = level[w]
                level[w] = 0
                x = w
                break
            if w == 1:
                stop = 0
                break

array.sort()
a = array[0]

def is_prime_num(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

while not is_prime_num(a):
    a += 1

print(a)