{"problem":{"name":"Subsequence Path","description":{"content":"There are $N$ towns numbered $1, \\dots, N$, and $M$ roads numbered $1, \\dots, M$.   Every road is directed; road $i$ $(1 \\leq i \\leq M)$ leads you from Town $A_i$ to Town $B_i$. The length of road $i$","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc271_e"},"statements":[{"statement_type":"Markdown","content":"There are $N$ towns numbered $1, \\dots, N$, and $M$ roads numbered $1, \\dots, M$.  \nEvery road is directed; road $i$ $(1 \\leq i \\leq M)$ leads you from Town $A_i$ to Town $B_i$. The length of road $i$ is $C_i$.\nYou are given a sequence $E = (E_1, \\dots, E_K)$ of length $K$ consisting of integers between $1$ and $M$. A way of traveling from town $1$ to town $N$ using roads is called a **good path** if:\n\n*   the sequence of the roads' numbers arranged in the order used in the path is a subsequence of $E$.\n\nNote that a subsequence of a sequence is a sequence obtained by removing $0$ or more elements from the original sequence and concatenating the remaining elements without changing the order.\nFind the minimum sum of the lengths of the roads used in a good path.  \nIf there is no good path, report that fact.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq M, K \\leq 2 \\times 10^5$\n*   $1 \\leq A_i, B_i \\leq N, A_i \\neq B_i \\, (1 \\leq i \\leq M)$\n*   $1 \\leq C_i \\leq 10^9 \\, (1 \\leq i \\leq M)$\n*   $1 \\leq E_i \\leq M \\, (1 \\leq i \\leq K)$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$A_1$ $B_1$ $C_1$\n$\\vdots$\n$A_M$ $B_M$ $C_M$\n$E_1$ $\\ldots$ $E_K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc271_e","tags":[],"sample_group":[["3 4 4\n1 2 2\n2 3 2\n1 3 3\n1 3 5\n4 2 1 2","4\n\nThere are two possible good paths as follows:\n\n*   Using road $4$. In this case, the sum of the length of the used road is $5$.\n*   Using road $1$ and $2$ in this order. In this case, the sum of the lengths of the used roads is $2 + 2 = 4$.\n\nTherefore, the desired minimum value is $4$."],["3 2 3\n1 2 1\n2 3 1\n2 1 1","\\-1\n\nThere is no good path."],["4 4 5\n3 2 2\n1 3 5\n2 4 7\n3 4 10\n2 4 1 4 3","14"]],"created_at":"2026-03-03 11:01:13"}}