题目描述

小 R 正在规划一次定向越野赛。场地可以被看作一个 $n$ 个点 $m$ 条边的带权简单无向图，$(x,y)$ 这条边的边权 $w(x,y)$ 表示走过这条路所需的时间。

为了防止过多同学走同一条路径出现相互干扰，所有参赛同学将被分为 2 组，每组分别比赛。

他已经规划出了一条简单路径 $v_1\to v_2\to \dots \to v_k$，作为第一组同学的参赛路径。现在他想找到另一条简单路径 $a_1\to a_2\to \dots\to a_l$，满足

1. 为了公平，两条比赛路线的长度需要相同，也即 $\sum_{1\le i\lt k}w(v_i,v_{i+1})=\sum_{1\le i\lt l}w(a_i,a_{i+1})$。
2. 两条比赛路线不能完全相同，也即 $k\ne l$，或 $k=l$ 但 $\exists 1\le i\le k,a_i\ne v_i$。

请你帮帮小 R，找到满足要求的一条路径 $a_1\to a_2\to \dots\to a_l$ 或者判断这样的路径不存在。

输入格式

第一行两个正整数 $n,m\ (1\le n\le 10^5,0\le m\le 5\times 10^5)$。

接下来 $m$ 行，每行三个正整数 $x,y,w\ (1\le x,y\le n,1\le w\le 10^{13})$，表示一条边 $(x,y)$，权值为 $w(x,y)=w$。保证给出的图是简单图。

接下来一行一个正整数 $k\ (1\le k\le n)$。

接下来一行 $k$ 个互不相同的正整数 $v_1,\dots,v_k\ (1\le v_i\le n)$。保证 $v_1\to v_2\to \dots \to v_k$ 确实是合法的简单路径。

输出格式

若满足要求的路径不存在，输出 -1。

否则，第一行输出一个正整数 $l\ (1\le l\le n)$。

接下来一行 $l$ 个互不相同的正整数 $a_1,\dots,a_l\ (1\le a_i\le n)$。

你需要保证 $a_1\to a_2\to \dots\to a_l$ 是满足题面要求的简单路径。

Problem Description

Little R is planning an orienteering competition. The venue can be represented as a weighted simple undirected graph with $n$ nodes and $m$ edges, where the weight $w(x, y)$ of edge $(x, y)$ represents the time required to go along this path from $x$ to $y$ (or from $y$ to $x$).

To prevent too many participants from taking the same path and causing interference, all participants will be divided into 2 groups, and each group will compete separately.

He has already planned a simple path $v_1 \to v_2 \to \dots \to v_k$ as the competition path for the first group. Now, he wants to find another simple path $a_1 \to a_2 \to \dots \to a_l$ that satisfies the following conditions:

1. For fairness, the lengths of the two competition paths must be the same, i.e., $\sum_{1 \le i < k} w(v_i, v_{i+1}) = \sum_{1 \le i < l} w(a_i, a_{i+1})$.
2. The two competition paths cannot be identical, i.e., either $k \ne l$, or $k = l$ but $\exists 1 \le i \le k, a_i \ne v_i$.

Please help Little R find such a path $a_1 \to a_2 \to \dots \to a_l$ or determine that such a path does not exist.

Input Format

The first line contains two positive integers $n, m\ (1 \le n \le 10^5, 0 \le m \le 5 \times 10^5)$.

The next $m$ lines each contain three positive integers $x, y, w\ (1 \le x, y \le n, 1 \le w \le 10^{13})$, representing an edge $(x, y)$ with weight $w(x, y) = w$. It is guaranteed that the given graph is a simple graph.

The next line contains a positive integer $k\ (1 \le k \le n)$.

The following line contains $k$ distinct positive integers $v_1, \dots, v_k\ (1 \le v_i \le n)$. It is guaranteed that $v_1 \to v_2 \to \dots \to v_k$ is indeed a valid simple path.

Output Format

If no such path exists, output -1.

Otherwise, the first line should contain a positive integer $l\ (1 \le l \le n)$.

The next line should contain $l$ distinct positive integers $a_1, \dots, a_l\ (1 \le a_i \le n)$.

You must ensure that $a_1 \to a_2 \to \dots \to a_l$ is a valid simple path that meets the requirements.

样例输入

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

样例输出

5
1 3 2 5 4