No submission language available for this problem.

Background

Special for beginners, ^_^

Description

一个国家有 $n$ 个城市编号为 $1$ 至 $n$，被已有的 $m$ 条单向高速公路连接，每条高速公路有一个长度 $len$。现在政府决定建造新的高速公路，在此之前，需要你将已有的公路信息存储并提供查询。一共将会有 $q$ 次查询，每次查询一个城市 $x$，输出所有以城市 $x$ 为起点的公路信息。

要求这些公路的终点互不相同，如果多个公路终点相同，则输出长度最小的那条公路的信息。

Format

Input

第一行 $3$ 个整数 $n,m,q$

接下来 $m$ 行每行三个整数 $x，y，len$

接下来 $q$ 行，每行一个整数 $x$

Output

对于每个查询，输出所有以 $x$ 为起点的公路的终点和距离

输出时，按照公路终点编号从小到大输出，具体参见样例。

Samples

4 4 3
1 2 3
1 2 4
1 2 5
3 4 1
1
3
4

2 3
4 1

4 3 1
1 4 3
1 2 2
1 3 1
1

2 2
3 1
4 3

Limitation

$0 < n,m,len \leq 2000,0 < x,y,z \leq n ,1 \leq q \leq 100$

1s, 1024KiB for each test case.