# 转动的字节

预估时间限制：4 秒。内存限制：4096 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

你齿轮上转动的字节，是我此生不变的信仰。

巴贝奇终究没能完成他的分析机。后来，采用电磁继电器的电动计算机，以及采用电子管、晶体管和半导体器件的电子计算机相继出现，以另一种方式实现了他的毕生夙愿。

## 形式化问题描述

有一个 $n$ 个结点、$m$ 条边的有向图，结点编号为 $1,\ldots,n$ .每个结点和每条边都有一个非空二进制字符串标签。结点一是终点，另给出 $k$ 个不同的可选起点，均不为一。允许重边和自环。

路径字符串依次连接起点标签、第一条边标签、下一个结点标签，直到终点标签。按照以下优先级选择路径：

1. 从某个可选起点到结点一，路径字符串长度最小。
2. 在长度最小的路径中，路径字符串的字典序最小，字符 `0` 小于 `1` .
3. 在前两项均相同的路径中，将经过的结点编号**从终点到起点**排列，使该编号序列字典序最小。每个编号作为一个整数比较，不按它的十进制字符比较。

序列的字典序比较在第一个不同位置决定大小；若一个是另一个的真前缀，则较短者较小。输出所选路径的正向字符串及正向结点序列。若不同重边给出完全相同的两项输出，不必区分这些边。保证至少存在一条可行路径。

## 输入格式

第一行三个整数 $n,m,k$ .第二行 $n$ 个字符串，依次为结点标签。第三行 $k$ 个起点编号。接下来 $m$ 行，每行两个整数 $u,v$ 和一个字符串 $s$ ，表示从 $u$ 到 $v$ 的有向边及其标签。

## 输出格式

第一行输出正向路径字符串。第二行从起点到终点输出经过的结点编号，用空格分隔。

## 样例

### 样例 1

### 输入

```text
12 15 2
00 1 0 1 1 1 0 0 0 1 101 101
11 12
3 1 00000
2 1 1111
4 3 0
4 2 1
6 4 0
7 4 1
5 6 1
5 7 1
9 5 1
10 5 1
8 9 1
8 10 1
12 8 1
11 8 1
4 2 1
```

### 输出

```text
101101011101111111100
11 8 9 5 7 4 2 1
```

### 样例 2

### 输入

```text
4 4 1
0 0 0 0
4
4 3 0
3 1 0
4 2 0
2 1 0
```

### 输出

```text
00000
4 2 1
```

### 样例 3

### 输入

```text
3 3 2
01 1 0
2 3
2 1 0
3 1 1
3 3 0
```

### 输出

```text
0101
3 1
```

## 样例解释

样例一的完整有向图见下图；圆内为“编号 / 点标签”，边旁为边标签，两条 $4\to2$ 的平行边都画出。高亮路径为输出路径。样例二两条路线都产生五个零，但反向编号序列 $(1,2,4)$ 小于 $(1,3,4)$ .样例三两条直达路线字符数相同，从结点三出发的字符串更小，自环会增加长度。

![样例一的完整网络和所选路径](assets/sample.svg)

## 数据范围与保证

$2\le n\le2\times10^6$ , $1\le m\le3\times10^6$ , $1\le k\le n-1$ . 所有点、边标签长度均为一到五，只含 `0` 和 `1` .所有编号合法，且至少一个可选起点可达终点。

| 分值比例 | 额外条件 |
| --- | --- |
| 20% | $n,m\le10$ |
| 30% | $n\le1000$ , $m\le2000$ |
| 20% | $n\le300000$ , $m\le500000$ |
| 30% | 无额外条件 |