该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

走路的时候，日记非常喜欢用各种奇怪的方式衡量自己这次走路的效率。

题目描述

日记所在的城市有 $n$ 个路口和 $m$ 条连接两个路口的单向道路，且任何两个路口互相（直接或间接）可达。每条道路从第 $u_i$ 个路口通向第 $v_i$ 个路口，且名为 $w_i$。不知道为什么，日记离开一个路口就不能再回去了（也就是说图无环）。

从一个路口到另一个路口可能有很多种路径。一条路径的权值为这条路径经过的每条道路的名字依次相连，例如依次经过道路“awa”“qwq”“ovo”的路径的权值 $p$ 为“awaqwqovo”。

1. 有的时候，日记觉得更短的路更优秀，因此她最喜欢走权值 $p$ 的长度最短的路径。如果有多条路径具有相同的权值长度，她会优先走权值的字典序最小的那条。
2. 有的时候，日记又会觉得权值更小的路更优秀，因此她会直接优先走权值字典序最小的路径。

对于两个字符串 $s, t$，我们称 $s$ 的字典序比 $t$ 小，当且仅当 $\exists i \in [1, \max(|s|, |t|)]$ 满足 $s_1 = t_1, s_2 = t_2, \dots, s_{i-1} = t_{i-1}, s_i < t_i$。对于一个 $i > |s|$，定义 $s_i = \texttt{0}$，其中字符 $\texttt{0}$ 小于任何其它字符。

日记只会从自己的家所在路口（路口 $1$）出发，并去向第 $n$ 个路口。日记想知道，在上述两种情况下，她会优先走的那条路径的权值是什么。你能帮帮她吗？

形式化题意

日记所在城市的路口和道路可以分别抽象为点集 $V=[1,n] \cap \ N$ 和边集 $E=\{(u_1, v_1), (u_2, v_2), \dots, (u_m, v_m)\}$，它们组成有向无环图 $G(V, E)$。每条边 $(u_i, v_i) \in E$ 均有一个字符串权 $w_i$。

定义一条路径为有序 $k(k \geq 1)$ 元组 $(a_1, a_2, \dots, a_k)$，满足 $\forall 1 \leq i < k$，有 $v_{a_i} = u_{a_{i+1}}$。定义一条路径 $(a_1, a_2, \dots, a_k)$ 的权值为 $w_{a_1}, w_{a_2}, \dots, w_{a_k}$ 顺次连接的结果。

请求出在以下两种情况下点 $1$ 到点 $n$ 的最小权路径。

1. 对于两个字符串 $s, t$，$s < t$ 当且仅当 $|s| < |t| \vee (|s| = |t| \wedge (\exists i \in [1, \max(|s|, |t|)] \text{ s.t. } s_1 = t_1, s_2 = t_2, \dots, s_{i-1} = t_{i-1}, s_i < t_i))$。
2. 对于两个字符串 $s, t$，$s < t$ 当且仅当 $\exists i \in [1, \max(|s|, |t|)] \text{ s.t. } s_1 = t_1, s_2 = t_2, \dots, s_{i-1} = t_{i-1}, s_i < t_i$。

额外定义，对于字符串 $s$ 和整数 $i > |s|$，$s_i = \texttt{0}$，其中 $\texttt{0}$ 小于任何其它字符。

输入格式

第 $1$ 行，输入 $3$ 个正整数 $n, m$。

接下来 $m$ 行，每行输入 $2$ 个正整数 $u_i, v_i$ 和 $1$ 个只包含小写字母的字符串 $w_i$。

输出格式

输出 $1$ 行 $2$ 个字符串，分别代表在情况 $1$ 和 $2$ 时日记会优先走的路径的权值。数据保证，一定存在一条路径使得路口 $1$ 能够到达路口 $n$。

数据范围

本题设置 25 个测试点，每个测试点 4 分。同时，每个测试点满足一些限制，见下：

测试点编号	n \leq	m \leq	特殊性质
$1$	$10$	$50$	$r$
$2$
$3$	$100$	$1000$
$4$
$5$	$2000$	$4000$	$g$
$6$
$7$
$8$		$10^4$	$r$
$9$
$10$		$10^4$
$11$	$10^5$	$2\times 10^5$	$g$
$12$
$13$
$14$		$5\times 10^5$	$s(1)$
$15$
$16$
$17$
$18$			$s(2)$
$19$
$20$
$21$
$22$			$r$
$23$
$24$		$5\times 10^5$
$25$		$5\times 10^5$

特别地，特殊性质 g 代表：图为网格图；s(x) 代表：每条边的名（边权） $w_i$ 均满足 $|w_i| = x$；r 代表：数据随机生成。

网格图生成：设网格图尺寸为 $x \times y(xy=n)$，则网格图上每个节点 $(i, j)$ 向 $(i + 1, j)$ 及 $(i, j + 1)$ 连边（若其存在）。之后，将每个坐标映射为一个路口，保证 $(1, 1)$ 处映射为路口 $1$，$(x, y)$ 处映射为路口 $n$。额外保证 $|w_i| = 1$。

随机生成：先随机生成一个以 $1$ 为根的叶向树，即 $i$ 的父亲在 $[1, i-1]$ 中等概率随机选取，并从每个节点的父亲向其连边；再随机生成 $m - n + 1$ 条边：先随机取一个深度不最大的节点 $u$，再随机取一个深度严格大于它的点 $v$，并连边 $(u, v)$。额外保证 $|w_i| \leq 4$，并先等概率选取某个长度，再等概率选取该长度的一个合法字符串。

对全部数据，有 $1 \leq n \leq 10^5, n - 1 \leq m \leq 5 \times 10^5, |w_i| \leq 10^5, \sum |w_i| \leq 2 \times 10^6$。

输入样例 1

4 6
1 2 aa
1 3 b
1 4 c
2 3 d
2 4 dd
3 4 c

输出样例 1

c aadc