Hard Autograd for Algebraic Expressions

题目描述

You are given a directed graph with $n$ vertices (numbered $1$ to $n$) and $m$ edges. Each edge is labeled with either a positive integer, a plus sign ('+'), a multiplication sign ('*'), a left parenthesis ('('), or a right parenthesis (')').

Consider a path from vertex $u$ to vertex $v$. Concatenating the labels of the edges along the path (in the order they are traversed) yields a string $s$. We say the path forms a valid arithmetic expression if $s\in S$, where $S$ is generated by the following rules:

1. For every string $x$ representing a positive integer, $x\in S$.
2. If both $x$ and $y$ belong to $S$, $x\texttt{+}y$ and $x\texttt{*}y$ are in $S$.
3. If $x\in S$, $\texttt{(}x\texttt{)}\in S$.
4. There are no other strings in $S$.

For every ordered pair $(u, v)$ such that there exists at least one path from $u$ to $v$ forming a valid arithmetic expression, compute the minimum possible value (evaluated according to the standard arithmetic rules) of such an expression. If the minimum value exceeds $10^9$, cap it at $10^9$ (i.e., report $10^9$ for any value $\geq 10^9$).

Note that in this problem, concatenating two integers directly is not allowed. That is, if there are two edges $e_1=(1,2,\texttt{123})$, $e_2=(2,3,\texttt{234})$, the path $e_1e_2$ does not form a valid arithmetic expression.

输入格式

The first line contains a single integer $T$, the number of test cases.

For each test case:

• The first line contains two integers $n$ and $m$ ($1\leq n\leq 300$, $1\leq m\leq 10^6$), the number of vertices and the number of edges.
• Each of the following $m$ lines contains three integers $u, v, w$ ($1 \lt =u,v \lt =n$, $-3\leq w\leq 10^9$), describing a directed edge from vertex $u$ to vertex $v$. The label of the edge is interpreted as follows:
  • If $w \gt 0$: the edge is labeled with the positive integer $w$.
  • If $w=0$: the edge is labeled with '+'.
  • If $w=-1$: the edge is labeled with '*'.
  • If $w=-2$: the edge is labeled with '('.
  • If $w=-3$: the edge is labeled with ')'.

There may be multiple edges and loops (edges from a vertex to itself).

It is guaranteed that the sum of $n$ over all test cases does not exceed $300$, and the sum of $m$ over all test cases does not exceed $10^6$.

输出格式

For each test case, first print a single integer $K$ — the number of ordered pairs $(u, v)$ for which there exists at least one path from $u$ to $v$ forming a valid arithmetic expression.

Then output $K$ lines. Each line must contain three integers $u$, $v$, and $c$ ($1 \le u, v \le n$, $0 \le c \le 10^9$), meaning that the minimum value among all valid expressions on paths from $u$ to $v$ is $c$, capped at $10^9$.

The $K$ lines must be sorted in lexicographic order of the pair $(u, v)$: first by $u$ ascending, then by $v$ ascending.

样例输入 #1

3
2 1
1 2 42
3 3
1 2 3
2 3 0
3 1 4
4 4
1 2 -2
2 3 9
3 4 -3
1 3 8

样例输出 #1

1
1 2 42
3
1 1 7
1 2 3
3 1 4
3
1 3 8
1 4 9
2 3 9