{"problem":{"name":"Colorful MST","description":{"content":"Ringo has an undirected graph $G$ with $N$ vertices numbered $1,2,...,N$ and $M$ edges numbered $1,2,...,M$. Edge $i$ connects Vertex $a_{i}$ and $b_{i}$ and has a length of $w_i$. Now, he is in the m","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"asaporo2_a"},"statements":[{"statement_type":"Markdown","content":"Ringo has an undirected graph $G$ with $N$ vertices numbered $1,2,...,N$ and $M$ edges numbered $1,2,...,M$. Edge $i$ connects Vertex $a_{i}$ and $b_{i}$ and has a length of $w_i$.\nNow, he is in the middle of painting these $N$ vertices in $K$ colors numbered $1,2,...,K$. Vertex $i$ is already painted in Color $c_i$, except when $c_i = 0$, in which case Vertex $i$ is not yet painted.\nAfter he paints each vertex that is not yet painted in one of the $K$ colors, he will give $G$ to Snuke.\nBased on $G$, Snuke will make another undirected graph $G'$ with $K$ vertices numbered $1,2,...,K$ and $M$ edges. Initially, there is no edge in $G'$. The $i$\\-th edge will be added as follows:\n\n*   Let $x$ and $y$ be the colors of the two vertices connected by Edge $i$ in $G$.\n*   Add an edge of length $w_i$ connecting Vertex $x$ and $y$ in $G'$.\n\nWhat is the minimum possible sum of the lengths of the edges in the minimum spanning tree of $G'$? If $G'$ will not be connected regardless of how Ringo paints the vertices, print $-1$.\n\n## Constraints\n\n*   $1 \\leq N,M \\leq 10^{5}$\n*   $1 \\leq K \\leq N$\n*   $0 \\leq c_i \\leq K$\n*   $1 \\leq a_i,b_i \\leq N$\n*   $1 \\leq w_i \\leq 10^{9}$\n*   The given graph may NOT be simple or connected.\n*   All input values are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$c_1$ $c_2$ $...$ $c_{N}$\n$a_1$ $b_1$ $w_1$\n$:$\n$a_M$ $b_M$ $w_M$\n\n## Partial Scores\n\n*   In the test set worth $100$ points, $N = K$ and $c_i = i$.\n*   In the test set worth another $100$ points, $c_i \\neq 0$.\n*   In the test set worth another $200$ points, $c_i = 0$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"asaporo2_a","tags":[],"sample_group":[["4 3 3\n1 0 1 2\n1 2 10\n2 3 20\n2 4 50","60\n\n$G'$ will only be connected when Vertex $2$ is painted in Color $3$."],["5 2 4\n0 0 0 0 0\n1 2 10\n2 3 10","\\-1\n\nRegardless of how Ringo paints the vertices, two edges is not enough to connect four vertices as one."],["9 12 9\n1 2 3 4 5 6 7 8 9\n6 9 9\n8 9 6\n6 7 85\n9 5 545631016\n2 1 321545\n1 6 33562944\n7 3 84946329\n9 7 15926167\n4 7 53386480\n5 8 70476\n4 6 4549\n4 8 8","118901402"],["18 37 12\n5 0 4 10 8 7 2 10 6 0 9 12 12 11 11 11 0 1\n17 1 1\n11 16 7575\n11 15 9\n10 10 289938980\n5 10 17376\n18 4 1866625\n8 11 959154208\n18 13 200\n16 13 2\n2 7 982223\n12 12 9331\n13 12 8861390\n14 13 743\n2 10 162440\n2 4 981849\n7 9 1\n14 17 2800\n2 7 7225452\n3 7 85\n5 17 4\n2 13 1\n10 3 45\n1 15 973\n14 7 56553306\n16 17 70476\n7 18 9\n9 13 27911\n18 14 7788322\n11 11 8925\n9 13 654295\n2 10 9\n10 1 545631016\n3 4 5\n17 12 1929\n2 11 57\n1 5 4\n1 17 7807368","171"]],"created_at":"2026-03-03 11:01:14"}}