{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"题意:","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n \u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;迪斯尼乐园是一个大型的主题公园,有着丰富的娱乐设施,也有大量的游客。通常,你需要等待很长一段时间才有机会享受任何景点。FastPass是一种系统,允许您在某个特定位置领取FastPass票,并在相应的设施中使用它们以避免排长队。\n\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;在FastPass系统的帮助下,人们可以更有效地安排他/她的行程。你得到了整个公园的地图,还有一些你感兴趣的景点。如何在最短的时间内参观所有感兴趣的景点?\n\u003cbr\u003e 注意:从1号点出发,参观完所有感兴趣的景点后在返回1号点。\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"第一行包含一个整数T(1\u0026lt;\u003dT\u0026lt;\u003d25),指示测试用例的数量。\n\u003cbr\u003e每个测试用例包含几行。\n\u003cbr\u003e第一行包含三个整数N,M,K(1 \u003c\u003d N \u003c\u003d 50; 0 \u003c\u003d M \u003c\u003d N(N-1)/ 2; 0 \u003c\u003d K \u003c\u003d 8),表示位置数( 从1开始,而1是公园中唯一必须开始和结束旅行的大门),道路数量和感兴趣的景点数量。\n\u003cbr\u003e下面的M行包含三个整数A,B,D(1 \u0026lt;\u003d A,B \u0026lt;\u003d N;0 \u0026lt;\u003d D \u0026lt;\u003d 10^4)这意味着从A到B需要D分钟的时间。\n\u003cbr\u003e接下来的K行分别包含几个整数P[i],T[i],FT[i],n[i],Fn[1], Fn[2], ..., Fn[n[i]],(1 \u003c\u003d P[i],N[i],fn[i] \u003c\u003d N,0 \u003c\u003d FT[i]\u003c \u003d T[i] \u003c\u003d 10 ^ 4),这意味着第i个感兴趣的景点位于P[i]位置,并且有n[i]个位置:Fn[1], Fn[2], ..., Fn[n[i]],您可以在第Fn[j]个景点中免费获得第i个感兴趣景点的FastPass 。 如果您通过它的FastPass来到第i个感兴趣的景点,则只需等待FT[i]分钟,否则就需要等待T[i]分钟。\n\u003cbr\u003e您可以假定所有位置均已连接,并且任何两个位置之间最多只有一条道路。\n\u003cbr\u003e注意在一个地点可能有几个景点。"}},{"title":"Output","value":{"format":"HTML","content":"\u003cbr\u003e对于输入中的每个测试用例,打印一行:“Case#X: Y”,其中X是测试用例编号(从1开始),Y是旅程的最小时间。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e2\n4 5 2\n1 2 8\n2 3 4\n3 4 19\n4 1 6\n2 4 7\n2 25 18 1 3\n4 12 6 1 3\n4 6 2\n1 2 5\n1 4 4\n3 1 1\n3 2 1\n3 4 1\n2 4 10\n2 8 3 1 4\n4 8 3 1 2\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003eCase #1: 53\nCase #2: 14\u003c/pre\u003e"}}]}