{"problem":{"name":"Modulo MST","description":{"content":"You are given a weighted simple connected undirected graph with $N$ vertices and $M$ edges, where vertices are numbered $1$ to $N$, and edges are numbered $1$ to $M$. Additionally, a positive integer ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc328_e"},"statements":[{"statement_type":"Markdown","content":"You are given a weighted simple connected undirected graph with $N$ vertices and $M$ edges, where vertices are numbered $1$ to $N$, and edges are numbered $1$ to $M$. Additionally, a positive integer $K$ is given.  \nEdge $i\\ (1\\leq i\\leq M)$ connects vertices $u_i$ and $v_i$ and has a weight of $w_i$.\nFor a spanning tree $T$ of this graph, the cost of $T$ is defined as the sum, modulo $K$, of the weights of the edges in $T$. Find the minimum cost of a spanning tree of this graph.\n\n## Constraints\n\n*   $2\\leq N\\leq8$\n*   $N-1\\leq M\\leq\\dfrac{N(N-1)}2$\n*   $1\\leq K\\leq10^{15}$\n*   $1\\leq u_i\\lt v_i\\leq N\\ (1\\leq i\\leq M)$\n*   $0\\leq w_i\\lt K\\ (1\\leq i\\leq M)$\n*   The given graph is simple and connected.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$u_1$ $v_1$ $w_1$\n$u_2$ $v_2$ $w_2$\n$\\vdots$\n$u_M$ $v_M$ $w_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc328_e","tags":[],"sample_group":[["5 6 328\n1 2 99\n1 3 102\n2 3 86\n2 4 94\n2 5 95\n3 4 81","33\n\nThe given graph is shown below:\n![image](https://img.atcoder.jp/abc328/67d2cc2b93ec47687a733cd379c3c07c.png)\nThe cost of the spanning tree containing edges $1,3,5,6$ is $(99+86+81+95)\\bmod{328}=361\\bmod{328}=33$. The cost of every spanning tree of this graph is at least $33$, so print $33$."],["6 5 998244353\n1 2 337361568\n1 6 450343304\n2 3 61477244\n2 5 745383438\n4 5 727360840","325437688\n\nPrint the cost of the only spanning tree of this graph, which is $325437688$."],["8 28 936294041850197\n1 2 473294720906780\n1 3 743030800139244\n1 4 709363019414774\n1 5 383643612490312\n1 6 557102781022861\n1 7 623179288538138\n1 8 739618599410809\n2 3 857687812294404\n2 4 893923168139714\n2 5 581822471860662\n2 6 740549363586558\n2 7 307226438833222\n2 8 447399029952998\n3 4 636318083622768\n3 5 44548707643622\n3 6 307262781240755\n3 7 12070267388230\n3 8 700247263184082\n4 5 560567890325333\n4 6 704726113717147\n4 7 588263818615687\n4 8 549007536393172\n5 6 779230871080408\n5 7 825982583786498\n5 8 713928998174272\n6 7 751331074538826\n6 8 449873635430228\n7 8 11298381761479","11360716373\n\nNote that the input and the answer may not fit into a $32\\operatorname{bit}$ integer."]],"created_at":"2026-03-03 11:01:14"}}