from collections import defaultdict, deque def calc(weight: int) -> int: q = deque([(0, 0)]) used = set() while q: v, step = q.popleft() if v == N-1: return step if v in used: continue used.add(v) for to, d in adj[v]: if weight > d: continue if to in used: continue q.append((to, step+1)) return -1 N, M = map(int, input().split()) adj = defaultdict(list) for _ in range(M): s, t, d = map(int, input().split()) s -= 1 t -= 1 adj[s].append((t, d)) adj[t].append((s, d)) lo = 1 hi = 10**9 limit = 0 step = 0 while lo <= hi: m = (lo + hi) // 2 s = calc(m) if s > 0: if limit < m: limit = m step = s lo = m + 1 else: hi = m - 1 print(limit, step)