'''
差分约束问题，用最长路求解每一个变量的最小值，最小值的总和
就是答案

'''


'''
SPFA算法，解带负权边的有向图和不带负权边的无向图的单源
最短路问题
'''
from collections import deque

class SPFA:

    # start_node 为起始点，edges是边的三元组(节点1， 节点2， 边权重) is_directed表示是否是有向图
    # 包含节点为1, 2, 3, 4, ..... max_node_num
    def __init__(self, start_node, edges, is_directed, max_node_num):
        self.edges = edges[::]
        self.start_node = start_node
        self.is_directed = is_directed
        self.max_node_num = max_node_num

    # 获取最短路径长度的列表[(节点1，长度1), (节点2, 长度2) .....]
    def getMinPathLen(self, reverse=False, m = 0):
        return self.getMinInfo(reverse, m)

    # reverse 为True的时候返回最长路
    def getMinInfo(self, reverse=False, m = 0):
        link = {}
        dis = [0x7fffffff] * (self.max_node_num+1) if reverse == False else [-0x7fffffff] * (self.max_node_num+1)
        dis[self.start_node] = 0


        for i in range(1, self.max_node_num):
            a, b, w = self.max_node_num, i, 1
            if not self.is_directed:
                # 无向图检查是否有负边
                if (reverse == False and w < 0) or (reverse == True and w > 0):
                    # 有正环或者负环情况下，提前退出
                    return None

                if a not in link:
                    link[a] = []
                if b not in link:
                    link[b] = []

                link[a].append((b, w))
                link[b].append((a, w))

            else:
                if a not in link:
                    link[a] = []
                link[a].append((b, w))

        for i in range(m):
            edges = []

            t, a, b = map(int, input().split())

            '''
            关系映射
            1, a, b: a >= b and b >= a
            2, a, b: b >= a+1
            3, a, b: a >= b
            4, a, b: a >= b+1
            5, a, b: b >= a
            '''

            if t == 1:
                edges.append((b, a, 0))
                edges.append((a, b, 0))
            elif t == 2:
                edges.append((a, b, 1))
            elif t == 3:
                edges.append((b, a, 0))
            elif t == 4:
                edges.append((b, a, 1))
            else:
                edges.append((a, b, 0))

            for a, b, w in edges:
                if not self.is_directed:
                    # 无向图检查是否有负边
                    if (reverse == False and w < 0) or (reverse == True and w > 0):
                        # 有正环或者负环情况下，提前退出
                        return None

                    if a not in link:
                        link[a] = []
                    if b not in link:
                        link[b] = []

                    link[a].append((b, w))
                    link[b].append((a, w))

                else:
                    if a not in link:
                        link[a] = []
                    link[a].append((b, w))


        updated_nodes = deque()
        updated_nodes.append(self.start_node)
        in_que = [0] * (self.max_node_num + 1)
        in_que[self.start_node] = 1

        # 进行V次迭代，第V次检查是否是无解情况
        iter_times = 0
        update_cnt = 0
        while iter_times < self.max_node_num:
            update_flag = False

            # 利用上一轮迭代距离变小的点进行松弛操作
            node_num = len(updated_nodes)
            for _ in range(node_num):
                a = updated_nodes.popleft()
                in_que[a] = 0
                if a not in link:
                    continue

                for b, w in link[a]:
                    new_dis = 0x7fffffff if dis[a] == 0x7fffffff else dis[a] + w
                    if (reverse == True and new_dis > dis[b]) or (reverse == False and new_dis < dis[b]):
                        dis[b] = new_dis
                        update_flag = True
                        update_cnt += 1
                        if update_cnt >= self.max_node_num * 3:     # 玄学剪枝
                            return None

                        if in_que[b] == 0:
                            in_que[b] = 1
                            updated_nodes.append(b)

            iter_times += 1

            if iter_times == self.max_node_num:
                if update_flag:
                    return None

            if not update_flag:
                break

        ans = 0
        for i in range(1, self.max_node_num+1):
            ans += dis[i]
        return ans

n, m = map(int, input().split())
algo = SPFA(n+1, [], is_directed=True, max_node_num=n+1)
max_len = algo.getMinPathLen(reverse=True, m = m)
#print(max_len)

if max_len is None:
    print(-1)
else:
    print(max_len)