{"problem":{"name":"Shortest Path Queries 2","description":{"content":"There are $N$ cities and $M$ roads in the Kingdom of Takahashi. The cities are numbered $1$ through $N$, and the roads are numbered $1$ through $M$. Road $i$ is a **one-way** road that leads from City","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc208_d"},"statements":[{"statement_type":"Markdown","content":"There are $N$ cities and $M$ roads in the Kingdom of Takahashi.\nThe cities are numbered $1$ through $N$, and the roads are numbered $1$ through $M$. Road $i$ is a **one-way** road that leads from City $A_i$ to City $B_i$, and it takes $C_i$ minutes to go through it.\nLet us define $f(s, t, k)$ as the answer to the following query.\n\n*   Compute the minimum time needed to get from City $s$ to City $t$. Here, other than the Cities $s$ and $t$, it is only allowed to pass through Cities $1$ through $k$. If City $t$ is unreachable or $s = t$, the answer should be $0$.\n\nCompute $f(s,t,k)$ for all triples $s,t,k$ and print the sum of them. More formally, print $\\displaystyle \\sum_{s = 1}^N \\sum_{t = 1}^N \\sum_{k = 1}^N f(s, t, k)$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 400$\n*   $0 \\leq M \\leq N(N-1)$\n*   $1 \\leq A_i \\leq N$ $(1 \\leq i \\leq M)$\n*   $1 \\leq B_i \\leq N$ $(1 \\leq i \\leq M)$\n*   $A_i \\neq B_i$ $(1 \\leq i \\leq M)$\n*   $1 \\leq C_i \\leq 10^6$ $(1 \\leq i \\leq M)$\n*   $A_i \\neq A_j$ or $B_i \\neq B_j$, if $i \\neq j$.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$ $C_1$\n$\\vdots$\n$A_M$ $B_M$ $C_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc208_d","tags":[],"sample_group":[["3 2\n1 2 3\n2 3 2","25\n\nThe triples $s,t,k$ such that $f(s,t,k) \\neq 0$ are as follows.\n\n*   For $k = 1$: $f(1,2,1) = 3, f(2,3,1) = 2$.\n*   For $k = 2$: $f(1,2,2) = 3, f(2,3,2) = 2, f(1,3,2) = 5$.\n*   For $k = 3$: $f(1,2,3) = 3, f(2,3,3) = 2, f(1,3,3) = 5$."],["3 0","0\n\nWe have $f(s,t,k) = 0$ for all $s,t,k$."],["5 20\n1 2 6\n1 3 10\n1 4 4\n1 5 1\n2 1 5\n2 3 9\n2 4 8\n2 5 6\n3 1 5\n3 2 1\n3 4 7\n3 5 9\n4 1 4\n4 2 6\n4 3 4\n4 5 8\n5 1 2\n5 2 5\n5 3 6\n5 4 5","517"]],"created_at":"2026-03-03 11:01:13"}}