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

题目描述

徐老师最近在复习最短路相关的算法——$Dijkstra$和 $Spfa$

最短路相关的题目往往会给出 $n$ 个节点，在这 $n$ 个节点之间存在 $m$ 条 单向边

其中第 $i$ 条边可以用 $u_i,v_i,w_i$ 描述，表示这条边从 $u_i$ 号节点出发，到达 $v_i$ 号节点，边权值为 $w_i$

最终题目会询问从 $1$ 号点到达 $n$ 号点的所有路径中，边权总和最小是多少。

但是徐老师觉得这样的最短路问题太老派了，于是他决定结合一下新的知识，出一个 融合题

于是徐老师决定，将每条边的边权修改为 字符串

例如徐老师如果依次经过边权分为别为 $aa,bb,ac$ 的边，那么这条路径的权值 $dis$ 即为 dis="aa"+"bb"+"ac"="aabbac"

现在徐老师想知道，对于给定的一个图，徐老师对于从 $1$ 号节点出发到达 $n$ 号节点的最短路提出了两个问题：

1. 字典序最小的路径权值是多少？
2. 长度最短的路径权值是多少？（如果存在多条长度最短的路径权值，则选择字典序最小的路径权值）

P.S. 对于两个字符串 $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}$ 小于任何其它字符。

输入格式

输入第一行包含两个整数 $n,m$ 表示节点数量和边数

接下来 $m$ 行，每行包含 $2$ 个整数 $u_i,v_i$ 和 $1$ 个字符串 $w_i$ 描述一条边的信息

特别的，保证输入的图一定无环，且输入的字符串中仅包含小写字母

输出格式

输出第一行包含一个字符串，表示第一个问题的答案

输出第二行包含一个字符串，表示第二个问题的答案

数据范围

$A:$ 数据随机生成

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

$C:$ $|w_i|=1$

$D:$ $|w_i|=2$

对全部数据满足 ：$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$。

样例输入

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

样例输出

aadc
c