题目描述

王国共有 $N$ 个城市（以 $1$、$2$、$\dots$、$N$ 为标记）和 $M$ 条双向道路。任何两个城市之间可能有几条道路，但没有任何道路连接同一个城市（没有环）。

你的任务是找到从城市 $1$ 到城市 $N$ 的最短路径，你经过的边的长度必须严格按照递增的顺序排列。

【简要题意】

给出一张 $n$ 个点，$m$ 条边的有向带权图，要求找一条从 $1$ 到 $n$ 且边权严格递增的最短路。

$1 \le n, m \le 10^5$.

输入格式

第一行中有一个整数 $T$（$1\le T\le500$），表示总共有 $T$ 个测试用例。

对于每个测试用例，有两个整数 $N$（$2\le N\le 10000$）和 $M$（$1\le M\le50000$），它们具有与上述相同的含义。

然后有 $M$ 条线，每条线中有三个整数 $x$（$1\le x\le N$）、$y$（$1 \le y \le N$）。

最多有十个测试用例满足 $N>200$ 或 $M>1000$。

输出格式

对于每个测试用例，您应该输出在上述任务中找到的最短路径的长度。 如果不存在这样的路径，您应该只输出No answer。

样例输入输出

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

10
No answer
No answer
1