from collections import deque
# ===================== INPUT =====================n, m = map(int, input().split())adj = [[] for _ in range(n + 1)]indeg = [0] * (n + 1)
for _ in range(m): u, v, *w = map(int, input().split()) if w: adj[u].append((v, w[0])) # có trọng số else: adj[u].append((v, 1)) # mặc định w = 1 indeg[v] += 1
# ===================== TOPO SORT (KAHN) =====================q = deque()for i in range(1, n + 1): if indeg[i] == 0: q.append(i)
topo = []while q: u = q.popleft() topo.append(u) for v, w in adj[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v)
# Kiểm tra có phải DAG khôngif len(topo) < n: print("Graph has cycle -> NOT DAG") exit()
# ===================== TEMPLATE 1: LONGEST PATH =====================INF = float('-inf')dp_longest = [INF] * (n + 1)
start = 1 # chỉnh tùy bàidp_longest[start] = 0
for u in topo: if dp_longest[u] == INF: continue for v, w in adj[u]: dp_longest[v] = max(dp_longest[v], dp_longest[u] + w)
# ===================== TEMPLATE 2: SHORTEST PATH =====================INF = float('inf')dp_shortest = [INF] * (n + 1)
dp_shortest[start] = 0
for u in topo: if dp_shortest[u] == INF: continue for v, w in adj[u]: dp_shortest[v] = min(dp_shortest[v], dp_shortest[u] + w)
# ===================== TEMPLATE 3: COUNT PATH =====================MOD = 10**9 + 7dp_count = [0] * (n + 1)
dp_count[start] = 1
for u in topo: for v, w in adj[u]: dp_count[v] = (dp_count[v] + dp_count[u]) % MOD
# ===================== OUTPUT DEMO =====================end = n # chỉnh tùy bài
print("Topo:", topo)print("Longest:", dp_longest[end])print("Shortest:", dp_shortest[end])print("Count:", dp_count[end])